English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the labeled multi-robot path planning problem in continuous 2D and3D domains in the absence of obstacles where robots must not collide with eachother. For an arbitrary number of robots in arbitrary initial and goalarrangements, we derive a polynomial time, complete algorithm that producessolutions with constant-factor optimality guarantees on both makespan anddistance optimality, in expectation, under the assumption that the robot labelsare uniformly randomly distributed. Our algorithm only requires a smallconstant factor expansion of the initial and goal configuration footprints forsolving the problem, i.e., the problem can be solved in a fairly small boundedregion. Beside theoretical guarantees, we present a thorough computationalevaluation of the proposed solution. In addition to the baselineimplementation, adapting an effective (but non-polynomial time) routingsubroutine, we also provide a highly efficient implementation that quicklycomputes near-optimal solutions. Hardware experiments on the microMVP platformcomposed of non-holonomic robots confirms the practical applicability of ouralgorithmic pipeline.

SEAR: A Polynomial-Time Multi-Robot Path Planning Algorithm with Expected Constant-Factor Optimality Guarantee