O3: An optimal and opportunistic path planner (with obstacle avoidance) using voronoi polygons
Abstract
Traditional mobile robot research focuses on a robot navigating its environment to reach a single goal while avoiding obstacles. This paper proposes a new method called O to solve the challenges presented at the Intelligent Ground Vehicle Competition (IGVC) where a navigation course includes multiple goals to be found in an optimal order. The O technique includes improvements on traditional path planning and obstacle avoidance techniques while providing an explicit ability to change course as obstacles are discovered. This method uses modern trajectories such as minimum-weighted Hamiltonian circuits, A* algorithm for obstacle avoidance, and local points of opportunity to update the globally optimal path using Voronoi polygons. Environmental mapping is also used to speed up the search algorithms in static environments. Overall, the O technique exploits local points of opportunity while avoiding obstacles and ultimately finding a globally optimal path through an unknown environment. This methodology will be implemented on an autonomous web-based tour guide robot to serve the Internet community reviewing Elizabethtown College. This methodology can be extended to other research areas where multiple locations need to be traversed independent of their order such as city map, trip planners, and distribution networks (power, internet, etc) due to its balance between weighted graphs and obstacle avoidance (objects, traffic, construction, etc). © 2008 IEEE. 3 3 3
