Reachability and Coverage Planning for Connected Agents: Extended Version
Motivated by the increasing appeal of robots in information-gathering missions, we study multi-agent path planning problems in which the agents must remain interconnected. We model an area by a topological graph specifying the movement and the connectivity constraints of the agents. We study the theoretical complexity of the reachability and the coverage problems of a fleet of connected agents on various classes of topological graphs. We establish the complexity of these problems on known classes, and introduce a new class called sight-moveable graphs which admit efficient algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimal Task and Motion Planning for Autonomous Systems Using Petri Nets
This study deals with the problem of task and motion planning of autonomous systems within the context of high-level tasks. Specifically, a task comprises logical requirements (conjunctions, disjunctions, and negations) …
Computational EfficiencyMotion PlanningTask and Motion PlanningGoal-Conditioned Reinforcement Learning with Disentanglement-based Reachability Planning
Goal-Conditioned Reinforcement Learning (GCRL) can enable agents to spontaneously set diverse goals to learn a set of skills. Despite the excellent works proposed in various fields, reaching distant goals in temporally e…
Disentanglementreinforcement-learningReinforcement LearningPRISM: Efficient and Locally Optimal Probabilistic Planning with Reachability Guarantees
Belief-space planning under motion uncertainty and state and control constraints remains a fundamental challenge, largely due to the difficulty of establishing reachability guarantees in constrained belief spaces. Existi…
Motion PlanningPlanning to Explore: Curiosity-Driven Planning for LLM Test Generation
The use of LLMs for code generation has naturally extended to code testing and evaluation. As codebases grow in size and complexity, so does the need for automated test generation. Current approaches for LLM-based test g…
Code GenerationGame-Theoretic Safe Multi-Agent Motion Planning with Reachability Analysis for Dynamic and Uncertain Environments (Extended Version)
Ensuring safe, robust, and scalable motion planning for multi-agent systems in dynamic and uncertain environments is a persistent challenge, driven by complex inter-agent interactions, stochastic disturbances, and model …
Collision AvoidanceMotion Planning