Path planning for unmanned vehicles using ant colony optimization on a dynamic voronoi diagram

One of the main objectives when planning paths for unmanned vehicles is to minimizing the time of arriving at the given destination while maximizing the safety of the vehicles. If the operational environment is static with perfect information, a safe and shortest path can be generated by applying a traditional optimization algorithm such as A*. However, if the environment is dynamic with uncertain information, an adaptive algorithm is favored. In this paper, we propose a biologically inspired path planning algorithm using the Ant Colony Optimization (ACO) on obstacle geometry described by the Voronoi diagram. Namely, the safe paths between obstacles are chosen as the boundaries of the Voronoi cells centered the obstacles. Based on the Voronoi diagram, ACO is then applied to produce quasioptimal paths. The combined Voronoi and ACO approach is expected to provide quasi-optimal paths adoptively to a dynamically changing environment. Our preliminary results confirm the effectiveness of our approach.