skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Spatial and Temporal Splitting Heuristics for Multi-Robot Motion Planning
In this work, we systematically examine the application of spatio-temporal splitting heuristics to the Multi-Robot Motion Planning (MRMP) problem in a graph-theoretic setting: a problem known to be NP-hard to optimally solve. Following the divide-and-conquer principle, we design multiple spatial and temporal splitting schemes that can be applied to any existing MRMP algorithm, including integer programming solvers and Enhanced Conflict Based Search, in an orthogonal manner. The combination of a good baseline MRMP algorithm with a proper splitting heuristic proves highly effective, allowing the resolution of problems 10+ times than what is possible previously, as corroborated by extensive numerical evaluations. Notably, spatial partition of problem fusing with the temporal splitting heuristic and the enhanced conflict based search (ECBS) algorithm increases the scalability of ECBS on large and challenging DAO maps by 5–15 folds with negligible impact on solution optimality.  more » « less
Award ID(s):
1845888 1734419
PAR ID:
10219065
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
IEEE International Conference on Robotics and Automation
ISSN:
1049-3492
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems)
    We consider a variant of the Multi-Agent Path-Finding problem that seeks both task assignments and collision-free paths for a set of agents navigating on a graph, while minimizing the sum of costs of all agents. Our approach extends Conflict-Based Search (CBS), a framework that has been previously used to find collision-free paths for a given fixed task assignment. Our approach is based on two key ideas: (i) we operate on a search forest rather than a search tree; and (ii) we create the forest on demand, avoiding a factorial explosion of all possible task assignments. We show that our new algorithm, CBS-TA, is complete and optimal. The CBS framework allows us to extend our method to ECBS-TA, a bounded suboptimal version. We provide extensive empirical results comparing CBS-TA to task assignment followed by CBS, Conflict-Based Min-Cost-Flow (CBM), and an integer linear program (ILP) solution, demonstrating the advantages of our algorithm. Our results highlight a significant advantage in jointly optimizing the task assignment and path planning for very dense cases compared to the traditional method of solving those two problems independently. For large environments with many robots we show that the traditional approach is reasonable, but that we can achieve similar results with the same runtime but stronger suboptimality guarantees. 
    more » « less
  2. ; ; ; ; ; (, Proceedings of the International Conference on Automated Planning and Scheduling)
    null (Ed.)
    Two popular optimal search-based solvers for the multi-agent pathfinding (MAPF) problem, Conflict-Based Search (CBS) and Increasing Cost Tree Search (ICTS), have been extended separately for continuous time domains and symmetry breaking. However, an approach to symmetry breaking in continuous time domains remained elusive. In this work, we introduce a new algorithm, Conflict-Based Increasing Cost Search (CBICS), which is capable of symmetry breaking in continuous time domains by combining the strengths of CBS and ICTS. Our experiments show that CBICS often finds solutions faster than CBS and ICTS in both unit time and continuous time domains. 
    more » « less
  3. ; (, Proceedings of the International Symposium on Combinatorial Search)
    Planning under time pressure arises in many situations. Real-time heuristic search, in which an agent must compute its next action within a prespecified time bound, has proven to be a useful model of real-time planning. However, it is laborious to prove the completeness of new real-time search algorithms. In this paper, we provide a general proof of the completeness of a standard real-time heuristic search algorithm in any problem domain that obeys the axioms of a cost algebra. The proof includes additional detail on how h values change as the algorithm learns. This foundation clarifies the dependence of the proof on domain and algorithm properties and will ease future applications of real-time planning. 
    more » « less
  4. ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    null (Ed.)
    Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazon. CBS is a lead- ing two-level search algorithm for solving MAPF optimally. ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS by sacrificing optimality and instead guaranteeing that the costs of its solutions are within a given factor of optimal. In this paper, we study how to decrease its runtime even further using inadmissible heuristics. Motivated by Explicit Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new bounded-suboptimal variant of CBS, that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements of CBS and adapt them to EECBS. We find that EECBS with the improvements runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances. We hope that the scalability of EECBS enables additional applications for bounded-suboptimal MAPF algorithms. 
    more » « less
  5. ; ; ; (, IEEE Vehicular Technology Conference)
    Unmanned aerial vehicles (UAVs) can supplement the existing ground-based heterogeneous cellular networks (Het-Nets), by replacing/supporting damaged infrastructure, providing real-time video support at the site of an emergency, offloading traffic in congested areas, extending coverage, and filling coverage gaps. In this paper, we introduce distributed algorithms that leverage UAV mobility, enhanced inter-cell interference coordination (ICIC), and cell range expansion (CRE) techniques defined in 3GPP Release-10 and 3GPP Release-11. Through Monte-Carlo simulations, we compare the system-wide 5th percentile spectral efficiency (5pSE) while optimizing the performance using a brute force algorithm, a heuristic-based sequential algorithm, and a deep Q-learning algorithm. The autonomous UAVs jointly optimize their location, ICIC parameters, and CRE to maximize 5pSE gains and minimize the outage probability. Our results show that the ICIC technique relying on a simple heuristic outperforms the ICIC technique based on deep Q-learning. Taking advantage of the multiple optimization parameters for interference coordination, the heuristic based ICIC technique can achieve 5pSE values that are reasonably close to those achieved with exhaustive brute force search techniques, at a significantly lower computational complexity. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email