Title

O3: An optimal and opportunistic path planner (with obstacle avoidance) using voronoi polygons

Document Type

Conference Proceeding

Publication Title

International Workshop on Advanced Motion Control, AMC

Publication Date

12-1-2008

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 O3 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 O3 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 O3 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.

Volume

1

First Page

371

Last Page

376

DOI

10.1109/AMC.2008.4516095

ISBN

9781424417032

Link to Full Text

Share

COinS