A Framework for Automatic Deployment of Robots in 2D and 3D Environments

We present a computational framework for automatic deployment of robots in 2D and 3D rectangular environments with polytopal obstacles. The results are derived for polytopal robots that can only translate with velocities restricted to polyhedral sets. Our approach consists of three steps: (1) constructing a discrete representation of the problem by using hierarchical partitions in the form of quad-trees and oct-trees, (2) planning the motion in the finite dimensional quotient produced by the partition, and (3) generating provably correct robot feedback control laws by constructing a hybrid system. Given the environment and robot geometry and constraints, generation of control laws is completely automated. The computation consists of polyhedral operations and searches on graphs