Optimal Multi-robot Task Planning: from Synthesis to Execution (and Back)

Francesco Leofante

Abstract

This paper presents a framework for multi-robot task planning that bridges the gap between high-level mathematical optimization and real-world execution. By leveraging Optimization Modulo Theories (OMT), the authors generate plans with formal performance guarantees and integrate them into a rule-based system capable of handling the unpredictable nature of a factory floor.

Introduction

In modern "smart factories," teams of autonomous robots must coordinate to move materials and manufacture goods. Traditionally, this coordination is handled in one of two ways: heuristic approaches, which are fast and flexible but offer no optimality guarantees, or formal planning, which provides optimal solutions but often struggles with the "messiness" of the real world, such as communication breaks or unexpected delays.

The authors address the challenge of integrated task planning and execution. They propose a system that doesn't just hand a robot a static "to-do" list, but rather synthesizes an optimal plan, monitors its execution in real-time, and provides feedback when things go off-script.

Methodology

The research builds on a technique called Planning as Satisfiability (PaS), where a planning problem is converted into a logic formula. The authors extend this in several key ways:

  1. Optimization Modulo Theories (OMT): Instead of just finding any valid plan, they use OMT to find the optimal plan based on specific rewards, such as minimizing time or maximizing throughput, utilizing the $\nu Z$ solver.
  2. Compact Encodings: To prevent logic formulas from becoming too large, they introduced a new structure that combines abstract state representations with "relaxations" of ordering properties. By not explicitly coding every possible sequence of events, the initial problem size remains manageable for the solver.
  3. CLIPS Integration: The high-level OMT planner is integrated with CLIPS, a rule-based production system. CLIPS acts as the "on-line executive," taking the optimal plan and managing the robots' moment-to-moment actions and monitoring.

Experimental Setup: RoboCup Logistics League

The primary testbed for this research is the RoboCup Logistics League (RCLL). This environment involves two main phases: Exploration (mapping the factory) and Production (fulfilling dynamic orders within specific time windows).

The RoboCup Logistics League (RCLL) simulation environment used for testing the multi-robot task planning framework.

The RCLL provides a simulated and physical environment where two teams of robots compete to manage logistics in a smart factory. The paper uses RCLL as a benchmark to compare their OMT approach against traditional PDDL-based planning and greedy rule-based systems.

Key Insights and Results

A significant finding is that removing explicit ordering constraints from the logical formula (the "Less is More" encoding) actually makes the system more efficient for large problems. While the solver works harder, the overall search space is significantly reduced.

The system successfully demonstrated that rigorous formal methods can provide mathematical proof of optimality even in highly dynamic environments. The "and Back" aspect of the framework refers to the runtime feedback loop, where execution data informs future planning cycles. Key results include:

  • Scalability: The compact encoding allowed the system to handle larger problem sizes more effectively than traditional methods.
  • Integration: A prototype successfully linked OMT synthesis with CLIPS-based agents used by world-champion RCLL teams.
  • Temporal Windows: The system modeled complex interactions, such as delivering products within specific time windows, a notoriously difficult planning challenge.

Conclusion and Future Work

While the current system uses simple rewards, future work aims to incorporate "Goal Reasoning," allowing robots to autonomously assess risk-reward trade-offs. Additionally, the authors plan to improve explainability by using "unsat cores" to generate human-readable explanations for robot decisions. Finally, efforts are underway to make the planner domain-independent, allowing it to be applied to any multi-robot logistics problem without custom coding.

Summary updated

Abstract

Integrated task planning and execution is a challenging problem with several applications in AI and robotics. In this work we consider the problem of generating and executing optimal plans for multi-robot systems under temporal and ordering constraints. More specifically, we propose an approach that unites the power of Optimization Modulo Theories with the flexibility of an on-line executive, providing optimal solutions for task planning, and runtime feedback on their execution.
BibTeX
@inproceedings{leofante2018optimal,
  author = {Francesco Leofante},
  title = {{Optimal Multi-robot Task Planning: from Synthesis to Execution (and Back)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/829},
}
Figure