CVT-based 2D motion planning with maximal clearance

Maximal clearance is an important property that is highly desirable in multi-agent motion planning. However, it is also inherently difficult to attain. We propose a novel approach to achieve maximal clearance by exploiting the ability of evenly distributing a set of points by a centroidal Voronoi tessellation (CVT). We adapt the CVT framework to multi agent motion planning by adding an extra time dimension and optimize the trajectories of the agents in the augmented domain. As an optimization framework, our method can work naturally on complex regions. We demonstrate the effectiveness of our algorithm in achieving maximal clearance in motion planning with some examples.

Authors

• Liping Zheng
• Yi-King Choi
• Xiaoping Liu 0003
• Wenping Wang

Keywords

• Planning
• Trajectory
• Optimization
• Robots
• Three dimensional displays
• Navigation
• Smoothing methods
• Path Planning
• Maximum Clearance
• Time Interval
• Optimization Problem
• Objective Function
• Energy Function
• Shortest Path
• Nonlinear Programming
• Inequality Constraints
• Time Instants
• Start Position
• Optimization Framework
• Speed Limit
• End Position
• Voronoi Diagram
• Points In Domain
• Extra Dimension
• Position Of Agent
• Trajectory Planning
• Trajectories Of Agents
• Speed Constraints