Formal design of robot Integrated Task and Motion Planning

Abstract

Integrated Task and Motion Planning (ITMP) for mobile robots becomes a new trend. Most existing methods for ITMP either restrict to static environments or lack performance guarantees. This motivates us to use formal design methods for mobile robots ITMP in a dynamic environment with moving obstacles. Our basic idea is to synthesize a global integrated task and motion plan through composing simple local moves and actions, and to achieve its performance guarantee through modular and incremental verifications. The design consists of two steps. First, reactive motion controllers are designed and verified locally. Then, a global plan is built upon these certified controllers by concatenating them together. In particular, we model the controllers and verify their safety through formulating them as Differential Dynamic Logic (dL) formula. Furthermore, these proven safe controllers are abstracted in Counter Linear Temporal Logic over Constraint System CLTLB(D) and composed based on an encoding to Satisfiability Modulo Theories (SMT) that takes into account the geometric constraints. Since dL allows compositional verification, the sequential composition of the safe motion primitives also preserves safety properties. Illustrative examples are presented to show the effectiveness of the method.