Generalizations of multi-agent path finding problem for incremental environments

Download

index.pdf

Date

2022-7-20

Author

Semiz, Fatih

Metadata

Show full item record

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

Item Usage Stats

306
views

26
downloads

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 problems. However, unlike the standard MAPF setting, in these problems there may be a need to replan agent paths while the movement of the agents continues. The need to replan agent paths may be due to the following reasons: packages falling on the road, passing of external vehicles, or new tasks added to the problem while the problem continues. Such situations can be better expressed with an incremental MAPF problem structure. In this thesis, we describe a MAPF variation where certain nodes on the map become temporarily impassable. We have created methods that effectively solve this problem definition and have proven through many experiments that they are effective solutions. We also defined a MAPF problem variation in which agents have multiple destinations in the lifelong MAPF problem structure. We have developed a new algorithm that solves the MAPF problem involving multiple destinations. For the task allocation problem, we created heuristic methods to minimize the total amount of travelled paths, and we tested these methods with many experiments and analyzed their performance.

Subject Keywords

Multi-agent path finding, Incremental planning, Task allocation, Heuristic search, Lifelong planning

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Real-time edge follow: A real-time path search approach Undeger, Cagatay; Polat, Faruk (2007-09-01) Real-time path search is the problem of searching a path from a starting point to a goal point in real-time. In dynamic and partially observable environments, agents need to observe the environment to track changes, explore to learn unknowns, and search suitable routes to reach the goal rapidly. These tasks frequently require real-time search. In this paper, we address the problem of real-time path search for grid-type environments; we propose an effective heuristic method, namely a real-time edge follow al...
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...
LIMP: Incremental Multi-agent Path Planning with LPA* Yorganci, Mucahit Alkan; Semiz, Fatih; Polat, Faruk (2022-01-01) 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 ...
Multi-objective path planning for virtual environments Oral, Tuğcem; Polat, Faruk; Department of Computer Engineering (2012) Path planning is a crucial issue for virtual environments where autonomous agents try to navigate from a specific location to a desired one. There are several algorithms developed for path planning, but several domain requirements make engineering of these algorithms difficult. In complex environments, considering single objective for searching and finding optimal or sub-optimal paths becomes insufficient. Thus, multi objective cases are distinguished and more complicated algorithms to be employed is requir...
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...

Citation Formats

F. Semiz, “Generalizations of multi-agent path finding problem for incremental environments,” Ph.D. - Doctoral Program, Middle East Technical University, 2022.