Towards an efficient optimal trajectory planner for multiple mobile robots

In this paper, we present a real-time algorithm that plans mostly optimal trajectories for multiple mobile robots in a dynamic environment. This approach combines the use of a Delaunay triangulation to discretise the environment, a novel efficient use of the A* search method, and a novel cubic spline representation for a robot trajectory that meets the kinematic and dynamic constraints of the robot. We show that for complex environments the shortest-distance path is not always the shortest-time path due to these constraints. The algorithm has been implemented on real robots, and we present experimental results in cluttered environments.