Multi-Robot Path Planning with Time Windows and Boolean Specifications

Abstract Path planning for multi-robot systems under complex task-logical specifications and strict temporal constraints poses significant combinatorial challenges. Existing approaches often handle logical and temporal requirements separately, limiting their scalability and practical applicability. To overcome this limitation, we propose a unified planning framework that seamlessly integrates Boolean specifications with time-window constraints. The problem is first formalized as a Mixed-Integer Linear Programming model that captures logical dependencies and timing requirements, including a collision avoidance module. To improve scalability for large-scale instances, we develop a Beam Search-based heuristic algorithm tailored for handling time windows. A similarity-based filtering mechanism is further incorporated to promote solution diversity and mitigate premature convergence. Experimental results demonstrate that the proposed approach achieves a desirable trade-off between computational efficiency and solution quality, offering a robust and scalable solution for multi-robot path planning under complex temporal-logical specifications.

Authors

Institutions

Publication Details

Journal
Research Square
Published
2026-11-16
DOI
https://doi.org/10.21203/rs.3.rs-9708502/v1
Primary Topic
Robotic Path Planning Algorithms
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Multi-Robot Path Planning with Time Windows and Boolean Specifications

Dimitri Lefebvre, Syrine Bouazza, Zhou He, Siyu LIU
4 links
Research Square
Robotic Path Planning Algorithms
preprint

Multi-Robot Path Planning with Time Windows and Boolean Specifications

Dimitri Lefebvre, Syrine Bouazza, Zhou He, Siyu LIU
preprint en

Abstract

Abstract Path planning for multi-robot systems under complex task-logical specifications and strict temporal constraints poses significant combinatorial challenges. Existing approaches often handle logical and temporal requirements separately, limiting their scalability and practical applicability. To overcome this limitation, we propose a unified planning framework that seamlessly integrates Boolean specifications with time-window constraints. The problem is first formalized as a Mixed-Integer Linear Programming model that captures logical dependencies and timing requirements, including a collision avoidance module. To improve scalability for large-scale instances, we develop a Beam Search-based heuristic algorithm tailored for handling time windows. A similarity-based filtering mechanism is further incorporated to promote solution diversity and mitigate premature convergence. Experimental results demonstrate that the proposed approach achieves a desirable trade-off between computational efficiency and solution quality, offering a robust and scalable solution for multi-robot path planning under complex temporal-logical specifications.

Research Square
Université Le Havre Normandie (FR), Shaanxi University of Science and Technology (CN)
Robotic Path Planning Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon