Multi-Agent Motion Planning from Signal Temporal Logic Specifications

Dawei Sun, Jingkai Chen, Sayan Mitra, Chuchu Fan

Research output: Contribution to journalArticlepeer-review

Abstract

We tackle the challenging problem of multi-agent cooperative motion planning for complex tasks described using signal temporal logic (STL), where robots can have nonlinear and nonholonomic dynamics. Existing methods in multi-agent motion planning, especially those based on discrete abstractions and model predictive control (MPC), suffer from limited scalability with respect to the complexity of the task, the size of the workspace, and the planning horizon. We present a method based on timed waypoints to address this issue. We show that timed waypoints can help abstract nonlinear behaviors of the system as safety envelopes around the reference path defined by those waypoints. Then the search for waypoints satisfying the STL specifications can be inductively encoded as a mixed-integer linear program. The agents following the synthesized timed waypoints have their tasks automatically allocated, and are guaranteed to satisfy the STL specifications while avoiding collisions. We evaluate the algorithm on a wide variety of benchmarks. Results show that it supports multi-agent planning from complex specification over long planning horizons, and significantly outperforms state-of-the-art abstraction-based and MPC-based motion planning methods. The implementation is available at https://github.com/sundw2014/STLPlanning.

Original languageEnglish (US)
Pages (from-to)3451-3458
Number of pages8
JournalIEEE Robotics and Automation Letters
Volume7
Issue number2
DOIs
StatePublished - Apr 1 2022

Keywords

  • Path planning for multiple mobile robots or agents
  • Task and motion planning

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Biomedical Engineering
  • Human-Computer Interaction
  • Mechanical Engineering
  • Computer Vision and Pattern Recognition
  • Computer Science Applications
  • Control and Optimization
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Multi-Agent Motion Planning from Signal Temporal Logic Specifications'. Together they form a unique fingerprint.

Cite this