Hierarchical Planning for Multi-Robot Systems in a Supervisory Control Context

This work explores the application of formal techniques to the synthesis of control logic for Multi-Robot Systems (MRS). The framework proposed in the paper is applied to a scenario where multiple autonomous mobile ground robots must work cooperatively to complete a set of tasks in minimal time, subject to constraints on the ordering of the tasks and restrictions on what regions a robot can occupy. Discrete event models and Supervisory Control Theory are employed to generate models defining the range of behaviors of the MRS that satisfy the given constraints. A number of planning algorithms including Greedy, Dijkstra's, Genetic, and Adaptive Large Neighborhood Search algorithms are then explored for selecting a “good” sequence of actions for the robots from among the set of legal alternatives. Specifically, the planning algorithms are applied to monolithic models, as well as to hierarchical models that split the problem into a high-level task assignment problem and a low-level motion planning problem. Formal methods are employed to justify the hierarchical model and the low-level motion planning employs a receding horizon approach to planning that composes modular models on the fly. The application of the described framework is applied to simulation of the MRS scenarios in Gazebo, as well as to implementation on physical mobile robots.