AO-ARC: Almost-Surely Asymptotically Optimal Multi-Robot Motion Planning with ARC
We present AO-ARC, an anytime multi-robot motion planning (MRMP) method that achieves initial solution times on par with state-of-the-art MRMP feasibility solvers while converging faster and more reliably than existing anytime MRMP methods as the number of robots increases. AO-ARC adapts the AO-x meta-algorithm for converting feasibility solvers into anytime algorithms by iteratively calling the original ARC method on bounded MRMP instances under a makespan cost metric. This exploits the adaptive (de)coupling of ARC while maintaining the consistent cost bound across robot (de)compositions needed for AO-x. We provide theoretical analysis proving the asymptotic optimality properties of AO- ARC and conduct empirical evaluation on a set of 2D scenarios with different levels of coordination complexity and a 3D manipulator scenario representative of real-world applications.
Code (0)
등록된 구현이 없습니다.
Tasks
Motion PlanningSimilar Papers 제목 키워드 기반
Revisiting Replanning from Scratch: Real-Time Incremental Planning with Fast Almost-Surely Asymptotically Optimal Planners
Robots operating in changing environments either predict obstacle changes and/or plan quickly enough to react to them. Predictive approaches require a strong prior about the position and motion of obstacles. Reactive app…
Sequential Portfolio Selection under Latent Side Information-Dependence Structure: Optimality and Universal Learning Algorithms
This paper investigates the investment problem of constructing an optimal no-short sequential portfolio strategy in a market with a latent dependence structure between asset prices and partly unobservable side informatio…
Asymptotically Efficient Quasi-Newton Type Identification with Quantized Observations Under Bounded Persistent Excitations
This paper is concerned with the optimal identification problem of dynamical systems in which only quantized output observations are available under the assumption of fixed thresholds and bounded persistent excitations. …
Chance Constrained Stochastic Optimal Control Based on Sample Statistics With Almost Surely Probabilistic Guarantees
While techniques have been developed for chance constrained stochastic optimal control using sample disturbance data that provide a probabilistic confidence bound for chance constraint satisfaction, far less is known abo…
Collision AvoidanceA New Approach for Distributed Hypothesis Testing with Extensions to Byzantine-Resilience
We study a setting where a group of agents, each receiving partially informative private observations, seek to collaboratively learn the true state (among a set of hypotheses) that explains their joint observation profil…
Two-sample testing