Variable Sized Grid Cells for Rapid Replanning in Dynamic Environments

Rachel Kirby, Reid Simmons, and Jodi Forlizzi
Proceedings of the IEEE/RSJ International Conference on Intelligent RObots and Systems (IROS), September, 2009, pp. 4913-4918.


Download
  • Adobe portable document format (pdf) (523KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
This paper presents a method for improving the runtime of an optimal heuristic path planner (A*) so that it can run repeatedly, in real-time, in a dynamic environment. This is necessary for mobile robots navigating in dynamic environments that have moving obstacles with associated costs, such as personal space around people or buffer zones around dangerous vehicles. Our approach is to modify the search space used by the A* algorithm, increasing the size of grid cells further from the robot. This approach relies on the notion that only the area closest to the robot needs to be searched carefully; areas further from the robot can be searched more coarsely. Because the planner is assumed to run repeatedly as the robot moves, the robot will always have a fine-grained path defined for its next action. We have experimentally verified in simulation that this algorithm can be run in real-time and produces paths that are comparable to full-resolution planning.

Keywords
planning

Notes
Associated Project(s): Human-Robot Interaction

Text Reference
Rachel Kirby, Reid Simmons, and Jodi Forlizzi, "Variable Sized Grid Cells for Rapid Replanning in Dynamic Environments," Proceedings of the IEEE/RSJ International Conference on Intelligent RObots and Systems (IROS), September, 2009, pp. 4913-4918.

BibTeX Reference
@inproceedings{Kirby_2009_6481,
   author = "Rachel Kirby and Reid Simmons and Jodi Forlizzi",
   title = "Variable Sized Grid Cells for Rapid Replanning in Dynamic Environments",
   booktitle = "Proceedings of the IEEE/RSJ International Conference on Intelligent RObots and Systems (IROS)",
   pages = "4913-4918",
   month = "September",
   year = "2009",
}