Motion planning using binary space partitioning

Abstract

This work explores a method for path planning for a robot in an environment that consists of stationary and moving obstacles. The technique uses binary partitioning of the environment by the obstacles to establish and analyze the spatial relationship between robot and obstacles. Hyperplanes are used to obtain recursively a disjoint set of D-dimensional cells, with each cell designated as belonging to either the interior or the exterior of the set. An overt idea of binary space partitioning as a representation of polytopes is given. Thus, the space-time configuration of free space is viewed as disjoint polytopes; each point in space-time is considered a map into a unique polytope. A traversal of the tree is used to obtain a linear order which gives the collision probability with the environment. Adjacent polytopes between the start and goal polytopes are then utilized to obtain a trajectory. Current implementation for a 2D static environment is discussed.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>