Reachability in multi-agent transfer systems
summary
Introduces a formal model of multi-agent reachability with energy transfers, distinguishes transfer-by-groups vs global transfer and synchronous/weak/asynchronous move semantics, and proves a full complexity map: many cases are PSPACE-complete (via a reduction from safe Petri nets using a controller encoding), some cases are NP-hard (subset-sum) or EXPSPACE and one variant is undecidable (reduction from Minsky machines). Key technical tools are an exponential energy bound to get PSPACE membership and concrete counterexamples showing global transfer can enable unbounded accumulation.
AI-written summary · about
chapters (12)
- 0:00Introduction to reachability in multi-agent transfer systems
- 1:04Single-agent model
- 3:13Multi-agent with transfers
- 5:01Three synchrony types
- 7:12Global transfer mode
- 8:16Complexity overview
- 11:28Transfer-by-groups focus
- 16:16PSPACE membership proof
- 19:53Petri nets reduction
- 23:28Undecidability via Minsky machine reduction
- 23:49Conclusion
- 25:14Question and answer session
related talks
40mCo-operative robots sharing the load
31mParameterized Verification of Systems with Precise (0,1)-Counter Abstraction
30mImplementing Grassroots Logic Programs with Multiagent Transition Systems and AI
13mCharacterizing Implementability of Global Protocols with Infinite States and Data
27mSymbolic Reachability Analysis of Distributed Systems using Narrowing and Heuristic Search
20mThe Complexity of Infinite-Horizon General-Sum Stochastic Games
20mImplementability of Global Distributed Protocols Modulo Network Architectures
01h 24mBuilding Multiagent Systems: An Ontology-Driven Approach with SPADE