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 extend the motion-planning-through-gadgets framework to several newscenarios involving various numbers of robots/agents, and analyze thecomplexity of the resulting motion-planning problems. While past work considersjust one robot or one robot per player, most of our models allow for one ormore locations to spawn new robots in each time step, leading to arbitrarilymany robots. In the 0-player context, where all motion is deterministicallyforced, we prove that deciding whether any robot ever reaches a specifiedlocation is undecidable, by representing a counter machine. In the 1-playercontext, where the player can choose how to move the robots, we proveequivalence to Petri nets, EXPSPACE-completeness for reaching a specifiedlocation, PSPACE-completeness for reconfiguration, and ACKERMANN-completenessfor reconfiguration when robots can be destroyed in addition to spawned.Finally, we consider a variation on the standard 2-player context where,instead of one robot per player, we have one robot shared by the players, alongwith a ko rule to prevent immediately undoing the previous move. We prove thisimpartial 2-player game EXPTIME-complete.

Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines