LIMP: Incremental Multi-agent Path Planning with LPA*

Date

2022-01-01

Author

Yorganci, Mucahit Alkan
Semiz, Fatih
Polat, Faruk

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

293
views

0
downloads

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.

Subject Keywords

AI, Multi-agent, Pathfinding, MAPF, Incremental Planning

URI

https://hdl.handle.net/11511/96830

DOI

https://doi.org/10.5220/0010824400003116

Conference Name

14th International Conference on Agents and Artificial Intelligence (ICAART)

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

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...
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...
ON PARAMETRIC LOWER BOUNDS FOR DISCRETE-TIME FILTERING Fritsche, Carsten; Orguner, Umut; Gustafsson, Fredrik (2016-03-25) Parametric Cramer-Rao lower bounds (CRLBs) are given for discrete-time systems with non-zero process noise. Recursive expressions for the conditional bias and mean-square-error (MSE) (given a specific state sequence) are obtained for Kalman filter estimating the states of a linear Gaussian system. It is discussed that Kalman filter is conditionally biased with a non-zero process noise realization in the given state sequence. Recursive parametric CRLBs are obtained for biased estimators for linear state esti...
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.