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

Generalizations of multi-agent path finding problem for incremental environments
Semiz, Fatih; Polat, Faruk; Department of Computer Engineering (2022-7-20)
Multi-Agent Path Finding problem (MAPF) is finding a path for multiple agents from a list of starting locations to a list of goal locations in such a way that the agents’ routes do not pass through the same location at the same time. The problem occurs in real-world during the transporting packages in warehouse environments with robots moving on rails, cleaning closed areas with cleaning robots, and protecting areas with multiple robots etc. It is usually sufficient to use discrete maps to express these pro...
A Multi-Objective Incremental Path Planning Algorithm for Mobile Agents
Oral, Tugcem; Polat, Faruk (2012-12-07)
Path planning is a crucial issue in unknown environments where an autonomous mobile agent has to reach a particular destination from some initial location. There are several incremental algorithms such as D-star[1], D-star Lite [2] that are able to ensure reasonable paths in terms of path length in unknown environments. However, in many real-world problems we realize that path length is not only the sole objective. For example in computer games, a non-player character needs to not only find a minimum cost p...
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...
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.