Graph-Based Multi Robot Motion Planning: Feasibility and Structural Properties
Ellips Masehian, Hamid Azadeh · InTech eBooks · 2011
Future generation autonomous agents are expected to operate in remote and dangerous places like outer space, undersea, hazardous waste sites, and are therefore anticipated to be far more self-directed than today's existing agents. The ability of an agent to plan its own motion is pivotal to its autonomy. For over more than three decades, agent motion planning in general, and robot motion planning in particular, have attracted much research in various fields and have become central topics in autonomous agents and artificial intelligence. Although today the term ‘motion planning’ is considered to cover a wide variety of problems, we will use it for the problem of planning collision-free motions for an autonomous robot moving among obstacles. The necessity of planning the motions of autonomous agents originally arose in early 1970’s, when the first industrial robots were to perform automatic tasks of manipulation and navigation. Soon it was realized that the complexity of the robot motion planning problem is PSPACE-hard and NP-complete since the size of the solution space grows exponentially and gets extremely complicated, especially for high degrees of freedom (Canny, 1988). Many techniques have been developed for solving the robot motion planning problem, including the ‘Skeleton’ or ‘Roadmap’ approach (Choset et al., 2005). In this approach, the continuous workspace is mapped into a one-dimensional graph with vertices including the start and goal of the robot, and edges as paths between vertices. This graph is then searched to find a collision-free start-to-goal path. Visibility Graph is a type of roadmap which is the collection of lines in the free space connecting vertices of an object to those of another (Fig. 1(a)). There are O(n2) edges in the Visibility Graph, and it can be constructed in O(n2) time and space in 2D, where n is the number of vertices. Voronoi Diagram is another roadmap defined as the set of points equidistant from two or more objects (Fig. 1(b)). The Voronoi Diagram partitions the space into regions, where each region contains one object. For each point in a region, the object within the region is the closest to that point than any other object. There are only O(n) edges in the Voronoi Diagram, and it can be efficiently constructed in Ω(nlogn) time, where n is the number of objects (Hwang & Ahuja, 1992). When multiple moving robots share a common workspace, the motion planning task becomes even more difficult and cannot be performed for just one robot without considering others. In this kind of problems, while pursuing their individual (local) goals,