A Graph-based Ant-like Approach to Optimal Path Planning

摘要

Motion planning of an autonomous mobile robot is involved in generating safe, optimal, short, and/or reasonable trajectories in its workspace and finally reaching its final target while avoiding collision with obstacles and escaping traps. This paper presents a new hybrid model to optimize trajectory of the global path of a mobile robot using a graph-based search algorithm associated with an ant colony optimization (ACO) method. Once a graph representing the robot workspace populated with obstacles is modelled by MAKLINK graph theory, Dijkstra algorithm is utilized to seek the sub-optimal collision-free robot trajectory. On the basis of the initial global sub-optimal trajectory generated by Dijkstra algorithm, the motion trajectory of the mobile robot is optimized in Cartesian space through the ACO method. Most importantly, a Bspline curve based smoothing scheme is, in a greater degree, applied to generate safer and smother trajectories with reasonable distance from obstacles. Results of simulation and comparison studies in various sorts of environments are addressed in order to demonstrate the superiority of the proposed hybrid graph-based model.