A Two-level Search Algorithm for Motion Planning

A two-level search algorithm for motion planning is presented in this paper. The algorithm combines a multiheuristic local search algorithm with a subgoal graph based global guidance. A novel feature of the planner is that it can adjust the balance between local and global planning. As the experimental data suggests that the optimal balance depends on the problem, a scheduling mechanism is added to the algorithm to adjust the balance during planning. The resulting motion planner is capable of solving very difficult motion planning problems. 1. Introduction In the basic variation of motion planning, the task is to generate a collision-free path for a movable object among known and static obstacles. A considerable amount of research has been conducted during the last two decades, but because of the hardness of the problem, no single overall method for motion planning is available. Therefore, research in robot motion planning remains as one of the important fields of study in the task o..