Flexible Binary Space Partitioning for Robotic Rescue

In domains such as robotic rescue, robots must plan paths through environments that are complex and dynamic, and in which robots have only incomplete knowledge. This will normally require both diversions from planned paths as well as significant re-planning as events in the domain unfold and new information is acquired. In terms of a representation for path planning, these requirements place significant demands on efficiency and flexibility. This paper describes a method for flexible binary space partitioning designed to serve as a basis for path planning in uncertain dynamic domains such as robotic rescue. This approach is used in the 2003 version of the Keystone Fire Brigade a robotic rescue team. We describe the algorithm used, make comparisons to related approaches to path planning, and provide an empirical evaluation of an implementation of this approach.