Moving bounding boxes and incremental synthesis for dynamic obstacles

Scott C. Livingston and Richard M. Murray
Submitted, 2014 International Conference on Robotics and Automation (ICRA)

While the use of formal synthesis for robotics problems in which the environment may act adversarially provides for exact—rather than probabilistic—correctness of controllers, such methods are impractical when the adversary can move freely in a large portion of the workspace. As is well-known, this is due to exponential growth in the state space with the addition of each new problem variable. Furthermore, such an approach is overly conservative because most configurations will not be reached in typical runs. Rather than entirely abandon the discrete game view, we propose a combined method that ensures exact satisfaction of a given specification, expressed in linear temporal logic, while providing a lower bound on robot-obstacle distance throughout execution. Our method avoids explicit encoding of the moving obstacle and thus substantially reduces the reactive synthesis problem size, while allowing other nondeterministic variables to still be included in the specification. Our approaches centers on modeling obstacle motion as changes in the presence of a virtual static obstacle, and performing incremental synthesis in response. The algorithm is tested in application to a planar surveillance task.

Conference Paper (PDF, 587K)
Downloading and printing FAQ