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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Multi-agent path planning is a challenging problem with numerous real-lifeapplications. Running a centralized search such as A* in the combined statespace of all units is complete and cost-optimal, but scales poorly, as thestate space size is exponential in the number of mobile units. Traditionaldecentralized approaches, such as FAR and WHCA*, are faster and more scalable,being based on problem decomposition. However, such methods are incomplete andprovide no guarantees with respect to the running time or the solution quality.They are not necessarily able to tell in a reasonable time whether they wouldsucceed in finding a solution to a given instance. We introduce MAPP, atractable algorithm for multi-agent path planning on undirected graphs. Wepresent a basic version and several extensions. They have low-polynomialworst-case upper bounds for the running time, the memory requirements, and thelength of solutions. Even though all algorithmic versions are incomplete in thegeneral case, each provides formal guarantees on problems it can solve. Foreach version, we discuss the algorithms completeness with respect to clearlydefined subclasses of instances. Experiments were run on realistic game gridmaps. MAPP solved 99.86% of all mobile units, which is 18--22% better than thepercentage of FAR and WHCA*. MAPP marked 98.82% of all units as provablysolvable during the first stage of plan computation. Parts of MAPPs computationcan be re-used across instances on the same map. Speed-wise, MAPP iscompetitive or significantly faster than WHCA*, depending on whether MAPPperforms all computations from scratch. When data that MAPP can re-use arepreprocessed offline and readily available, MAPP is slower than the very fastFAR algorithm by a factor of 2.18 on average. MAPPs solutions are on average20% longer than FARs solutions and 7--31% longer than WHCA*s solutions.

MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees