Algorithmic Advances in Planning and Control of Robotic Systems

This talk addresses the problem of “anytime” control strategy synthesis for dynamical systems, proposing a general framework based on the incremental refinement of a finite “concretization” of the system. We focus on the problem of designing a plan to fulfill a given task specification while satisfying a set of safety rules, and in particular to task specifications that become feasible only if a subset of the safety rules are violated. The proposed algorithm then computes a control law, that minimizes the level of unsafety for a trajectory that satisfies the given task specification. This problem is motivated by an autonomous car navigating an urban environment while following rules of the road such as “always travel in right lane” and “do not change lanes frequently,” or UAVs planning a mission balancing mission objectives, rules of engagements, and environmental constraints.  Ideas behind sampling based motion-planning algorithms, such as the Probabilistic Road Map (PRM) and Rapidly-exploring Random Tree (RRT), are employed to incrementally construct a finite concretization of the dynamics as a durational Kripke structure. In conjunction with this, a finite automaton that captures the safety rules is used in order to find an optimal trajectory that minimizes the violation of safety rules. It is shown that the proposed algorithm guarantees asymptotic optimality, i.e., almost-sure convergence to optimal solutions. The algorithms are demonstrated on an autonomous vehicle platform—showing perhaps for the first time the applicability of formal methods to full-scale, real-world robotic systems.