Multiple path planning using wavefront collision

The concept of wavefront expansion was introduced in order to build a collision-free path between two points among obstacles, minimizing a criterion. In this paper, we propose a new concept, called wavefront collision, in order to do the same for all possible paths between n waypoints. It consists in expanding simultaneously one wavefront by waypoint, until they collide. Using this concept, all paths can be computed thanks to one multiple wavefront expansion instead of n - 1, hence dividing the computational effort by about 3. 5.

Authors

• Michaël Soulignac
• Patrick Taillibert

Keywords

• Path planning
• Costs
• Shape
• Military computing
• Intelligent robots
• USA Councils
• Mobile robots
• Hazards
• Traveling salesman problems
• Wavefront Collisions
• Computational Effort
• Collision-free Path
• Multiple Expansion
• Grid Cells
• Expansion Phase
• Collision Cell
• Traveling Salesman Problem
• Hill-climbing
• Part Of Path