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.

Authors

• Jacky Baltes
• John Anderson 0001

Keywords

• Orbital robotics
• Path planning
• Navigation
• Mobile robots
• Autonomous agents
• Computer science
• Fires
• Partitioning algorithms
• Target tracking
• Measurement standards
• Spatial Partitioning
• Flexible Space
• Binary Partitioning
• Binary Space Partitioning
• Dynamic Domain
• Heuristic
• Open Space
• Tree Branches
• Information Gain
• Tree Structure
• Local Approach
• Leaf Node
• Visibility Graph
• Spatial Area
• Representation Of The Environment
• Odometry