MV*: A kinodynamic multi-agent path planning algorithm in unstructured environments

This paper presents MV*, a centralised kinodynamic multi-agent path planner for car-like vehicles that must coordinate in shared, unstructured environments with static obstacles. The method couples a velocity-aware single-agent lattice search, termed V*, with a priority-based coordination layer. Each single-agent search expands dynamically-feasible motions over position, heading, speed, and time, so that route and speed are decided jointly rather than in sequence, and waiting is represented as an explicit zero-velocity state. The coordination layer searches over acyclic priority orderings and uses branch-and-bound pruning to discard priority configurations that cannot improve the incumbent solution. When a conflict is encountered, the search branches based on alternative priority relations among the conflicting agents, while a scoring mechanism guides exploration toward more promising branches. For each branch, lower-priority agents are replanned around the trajectories of higher-priority agents until a conflict-free priority ordering is obtained. On the MVTP benchmark, the planner achieves substantially shorter runtimes while maintaining solution quality close to that of the reference optimisation solver. The scalability of MV* is further demonstrated on the CL-CBS benchmark, where it coordinates up to 100 vehicles within the prescribed time limit.

Institutions

Publication Details

Journal
Transportation Research Part C Emerging Technologies
Published
2026-11-15
DOI
https://doi.org/10.1016/j.trc.2026.106142
Primary Topic
Robotic Path Planning Algorithms
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

MV*: A kinodynamic multi-agent path planning algorithm in unstructured environments

1 links
Transportation Research Part C Emerging Technologies
Robotic Path Planning Algorithms
article

MV*: A kinodynamic multi-agent path planning algorithm in unstructured environments

article en

Abstract

This paper presents MV*, a centralised kinodynamic multi-agent path planner for car-like vehicles that must coordinate in shared, unstructured environments with static obstacles. The method couples a velocity-aware single-agent lattice search, termed V*, with a priority-based coordination layer. Each single-agent search expands dynamically-feasible motions over position, heading, speed, and time, so that route and speed are decided jointly rather than in sequence, and waiting is represented as an explicit zero-velocity state. The coordination layer searches over acyclic priority orderings and uses branch-and-bound pruning to discard priority configurations that cannot improve the incumbent solution. When a conflict is encountered, the search branches based on alternative priority relations among the conflicting agents, while a scoring mechanism guides exploration toward more promising branches. For each branch, lower-priority agents are replanned around the trajectories of higher-priority agents until a conflict-free priority ordering is obtained. On the MVTP benchmark, the planner achieves substantially shorter runtimes while maintaining solution quality close to that of the reference optimisation solver. The scalability of MV* is further demonstrated on the CL-CBS benchmark, where it coordinates up to 100 vehicles within the prescribed time limit.

Transportation Research Part C Emerging TechnologiesVol. 195
The University of Sydney (AU)
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