More Like this

1. Conflict-Based Search with Optimal Task Assignment

   Hoenig, W.; Kiesel, S.; Tinka, A.; Durham, J.; Ayanian, N. (January 2018, 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. Conflict-Based Increasing Cost Search

   Walker, Thayne T.; Sturtevant, Nathan R.; Felner, Ariel; Zhang, Han; Li, Jiaoyang; Kumar, T. K. (May 2021, 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. Distributed Approaches for Inter-Cell Interference Coordination in UAV-Based LTE-Advanced HetNets

   https://doi.org/10.1109/VTCFall.2018.8691002  

   Singh, Simran; Kumbhar, Abhaykumar; Guvenc, Ismail; Sichitiu, Mihail L (August 2018, 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
4. EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding

   Li, Jiaoyang; Ruml, Wheeler Ruml; Koenig, Sven (January 2021, 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. Rolling Horizon Based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows

   https://doi.org/10.1609/aaai.v37i4.25644  

   Kim, Youngseo; Edirimanna, Danushka; Wilbur, Michael; Pugliese, Philip; Laszka, Aron; Dubey, Abhishek; Samaranayake, Samitha (June 2023, Proceedings of the AAAI Conference on Artificial Intelligence)

   The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times. 

   more » « less