Path planning with uncertainty: Voronoi Uncertainty Fields
- 1 May 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10504729,p. 4596-4601
Abstract
In this paper, a two-level path planning algorithm that deals with map uncertainty is proposed. The higher level planner uses modified generalized Voronoi diagrams to guarantee finding a connected path from the start to the goal if a collision-free path exists. The lower level planner considers uncertainty of the observed obstacles in the environment and assigns repulsive forces based on their distance to the robot and their positional uncertainty. The attractive forces from the Voronoi nodes and the repulsive forces from the uncertainty-biased potential fields form a hybrid planner we call Voronoi Uncertainty Fields (VUF). The proposed planner has two strong properties: (1) bias against uncertain obstacles, and (2) completeness. We analytically prove the properties and run simulations to validate our method in a forest-like environment.Keywords
This publication has 16 references indexed in Scilit:
- The Belief Roadmap: Efficient Planning in Belief Space by Factoring the CovarianceThe International Journal of Robotics Research, 2009
- Path Planning for Autonomous Driving in Unknown Environments2009
- RRT-SLAM for motion planning with motion and map uncertainty for robot exploration2008
- Motion Planning for SLAM Based on Frontier Exploration2007
- Global A-Optimal Robot Exploration in SLAM2006
- A voronoi diagram‐visibility graph‐potential field compound algorithm for robot path planningJournal of Robotic Systems, 2004
- Probabilistic roboticsCommunications of the ACM, 2002
- Voronoi diagrams—a survey of a fundamental geometric data structureACM Computing Surveys, 1991
- Motion planning in a plane using generalized Voronoi diagramsIEEE Transactions on Robotics and Automation, 1989
- Generalization of Voronoi Diagrams in the PlaneSIAM Journal on Computing, 1981