In the context of robotics, configuration space （c- space） is widely used for non-circular robots to engage tasks such as path planning, collision check, and motion planning. In many real-time applications, it is im...In the context of robotics, configuration space （c- space） is widely used for non-circular robots to engage tasks such as path planning, collision check, and motion planning. In many real-time applications, it is important for a robot to give a quick response to the user＇s command. Therefore, a constant bound on planning time per action is severely im- posed. However, existing search algorithms used in c-space gain first move lags which vary with the size of the under- lying problem. Furthermore, applying real-time search algo- rithms on c-space maps often causes the robots being trapped within local minima. In order to solve the above mentioned problems, we extend the learning real-time search （LRTS） algorithm to search on a set of c-space generalized Voronoi diagrams （c-space GVDs）, helping the robots to incremen- tally plan a path, to efficiently avoid local minima, and to ex- ecute fast movement. In our work, an incremental algorithm is firstly proposed to build and represent the c-space maps in Boolean vectors. Then, the method of detecting grid-based GVDs from the c-space maps is further discussed. Based on the c-space GVDs, details of the LRTS and its implemen- tation considerations are studied. The resulting experiments and analysis show that, using LRTS to search on the c-space GVDs can 1） gain smaller and constant first move lags which is independent of the problem size; 2） gain maximal clear- ance from obstacles so that collision checks are much re- duced; 3） avoid local minima and thus prevent the robot from visually unrealistic scratching.展开更多
文摘In the context of robotics, configuration space （c- space） is widely used for non-circular robots to engage tasks such as path planning, collision check, and motion planning. In many real-time applications, it is important for a robot to give a quick response to the user＇s command. Therefore, a constant bound on planning time per action is severely im- posed. However, existing search algorithms used in c-space gain first move lags which vary with the size of the under- lying problem. Furthermore, applying real-time search algo- rithms on c-space maps often causes the robots being trapped within local minima. In order to solve the above mentioned problems, we extend the learning real-time search （LRTS） algorithm to search on a set of c-space generalized Voronoi diagrams （c-space GVDs）, helping the robots to incremen- tally plan a path, to efficiently avoid local minima, and to ex- ecute fast movement. In our work, an incremental algorithm is firstly proposed to build and represent the c-space maps in Boolean vectors. Then, the method of detecting grid-based GVDs from the c-space maps is further discussed. Based on the c-space GVDs, details of the LRTS and its implemen- tation considerations are studied. The resulting experiments and analysis show that, using LRTS to search on the c-space GVDs can 1） gain smaller and constant first move lags which is independent of the problem size; 2） gain maximal clear- ance from obstacles so that collision checks are much re- duced; 3） avoid local minima and thus prevent the robot from visually unrealistic scratching.
