LIMP: Incremental Multi-agent Path Planning with LPA*

2022-01-01
Yorganci, Mucahit Alkan
Semiz, Fatih
Polat, Faruk
The multi-agent pathfinding (MAPF) problem is defined as finding conflict-free paths for more than one agent. There exist optimal and suboptimal solvers for MAPF, and most of the solvers focus on the MAPF problem in static environments, but the real world is far away from being static. Motivated by this requirement, in this paper, we introduce an incremental algorithm to solve MAPF. We focused on discrete-time and discrete space environments with the unit cost for all edges. We proposed an algorithm called incremental multi-agent path planning with LPA* (LIMP) and discrete lifelong planning A* (DLPA*) for solving I-MAPF (Incremental MAPF). LIMP is the combination of two algorithms which are the Conflict Based Search D*-lite (CBS-D*lite) (Semiz and Polat, 2021) and DLPA*. DLPA* is just a tailored version of the lifelong planning A* (Koenig et al., 2004) which is an incremental search algorithm for one agent. We have shown that LIMP outperforms Conflict Based Search replanner (CBS-replanner) and CBS-D*-lite (Semiz and Polat, 2021) in terms of speed. Moreover, in terms of cost, LIMP and CBS-D*-lite perform similarly, and they are close to CBS-replanner.
14th International Conference on Agents and Artificial Intelligence (ICAART)

Suggestions

Multiresolution formation preserving path planning in 3-D virtual environments
Hoşgör, Can; Polat, Faruk; Department of Computer Engineering (2011)
The complexity of the path finding and navigation problem increases when multiple agents are involved and these agents have to maintain a predefined formation while moving on a 3-D terrain. In this thesis, a novel approach for multiresolution formation representation is proposed, that allows hierarchical formations of arbitrary depth to be defined using different referencing schemes. This formation representation approach is then utilized to find and realize a collision free optimal path from an initial loc...
Fano-control of down-conversion in a nonlinear crystal via plasmonic-quantum emitter hybrid structures
Artvin, Zafer; Gunay, Mehmet; Bek, Alpan; TAŞGIN, MEHMET EMRE (The Optical Society, 2020-12-01)
Control of the nonlinear response of nanostructures via path interference effects, i.e., Fano resonances, has been studied extensively. In such studies, a frequency conversion process takes place near a hot spot. Here, we study the case where the frequency conversion process takes place along the body of a nonlinear crystal. Metal nanoparticle-quantum emitter dimers control the down-conversion process, taking place throughout the crystal body, via introducing interfering conversion paths. Dimers behave as i...
Assignment problem and its variations
Gülek, Mehmet; Toroslu, İsmail Hakkı; Department of Computer Engineering (2007)
We investigate the assignment problem, which is the problem of matching two sets with each other, optimizing a given function on the possible matchings. Among different definitions, a graph theoretical definition of the linear sum assignment problem is as follows: Given a weighted complete bipartite graph, find a maximum (or minimum) one-to-one matching between the two equal-size sets of the graph, where the score of a matching is the total weight of the matched edges. We investigate extensions and variatio...
Quasi-fission and fusion-fission reactions in Ca-48+Pb-208 collisions at E-c.m.=190 MeV
Yilmaz, O.; Turan, Gürsevil; Yilmaz, B. (Springer Science and Business Media LLC, 2020-02-05)
The yields of quasifission fragments in the Ca-48+Pb-208 are investigated in the framework of the stochastic mean field (SMF) approach based on the Skyrme-TDHF calculations. A method which combines the microscopic time-dependent Hartree-Fock (TDHF) theory with a statistical de-excitation model, GEMINI++, is used for calculating the yields of fusion-fission fragments after de-excitation processes of primary reaction products which is assumed to be dominated by neutron emission in the present system. Results ...
Robust semi supervised clustering with polyhedral and circular uncertainty
Dinler, Derya; Tural, Mustafa Kemal (null; 2016-07-03)
We consider a semi-supervised clustering problem where the locations of the data objects are subject to uncertainty. Each uncertainty set is assumed to be either a closed convex bounded polyhedron or a closed disk. The final clustering is expected to be in accordance with a given number of instance level constraints. The objective function considered minimizes the total of the sum of the violation costs of the unsatisfied instance level constraints and a weighted sum of squared maximum Euclidean distances b...
Citation Formats
M. A. Yorganci, F. Semiz, and F. Polat, “LIMP: Incremental Multi-agent Path Planning with LPA*,” presented at the 14th International Conference on Agents and Artificial Intelligence (ICAART), ELECTR NETWORK, 2022, Accessed: 00, 2022. [Online]. Available: https://hdl.handle.net/11511/96830.