Incremental multi-agent path finding

Date

2021-03-01

Author

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

400
views

0
downloads

Existing multi-agent path finding (MAPF) algorithms are offline methods that aim at finding conflict-ree paths for more than one agent. In many real-life applications it is possible that a multi-agent plan cannot be fully executed due to some changes in the environment (represented as a graph), or in missions in which the agents are involved. Even in the case of a minor change, the offline planning algorithm must be re-started from scratch to generate a new plan, and this often requires a substantial amount of time. Motivated by this real-life requirement, we introduced the Incremental Multi-Agent Path Finding (I-MAPF) problem. Any location (node) in the initial environment (graph) can become unavailable for some time and then become available again. Agents can be informed about these changes before they occur and some agents have to update their plans if they planned to use that location. The Conflict Based Search (CBS) is one of most the successful algorithms in solving MAPF problems. To our best knowledge, there are no currently existing studies that attempt at solving the I-MAPF problem. In this paper, we propose a new method to solve the I-MAPF problem, called CBS-D*-lite. CBS-D*-lite is built upon CBS and avoids re-planning for agents that are not affected by the environmental changes. To achieve this, CBS-D*-lite employs D*-lite, an incremental single-agent pathfinding algorithm as the lower-level search method in CBS. We show that the number of time-steps required to solve a problem is generally lower than with regular CBS. Empirically, we show that the CBS-D*-lite provided faster results than regular CBS, and the total cost provided CBS-D*-lite is generally close to the total cost values provided by the regular CBS when there are environmental changes. (C) 2020 Elsevier B.V. All rights reserved.

Subject Keywords

Computer Networks and Communications, Hardware and Architecture, Software

URI

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

Journal

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE

DOI

https://doi.org/10.1016/j.future.2020.09.032

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

A systematic approach to the integration of overlapping partitions in service-oriented data grids Sunercan, H. Kevser; Alpdemir, M. Nedim; Çiçekli, Fehime Nihan (Elsevier BV, 2011-06-01) This paper aims to provide a service-oriented data integration solution over data Grids for cases where distributed data sources are partitioned with overlapping sections of various proportions. This is an interesting variation which combines both replicated and partitioned data within the same data management framework. Thus, the data management infrastructure has to deal with specific challenges regarding the identification, access and aggregation of partitioned data with varying proportions of overlappin...
A temporal neural network model for constructing connectionist expert system knowledge bases Alpaslan, Ferda Nur (Elsevier BV, 1996-04-01) This paper introduces a temporal feedforward neural network model that can be applied to a number of neural network application areas, including connectionist expert systems. The neural network model has a multi-layer structure, i.e. the number of layers is not limited. Also, the model has the flexibility of defining output nodes in any layer. This is especially important for connectionist expert system applications.
Path planning for mobile-anchor based wireless sensor network localization: Static and dynamic schemes Erdemir, Ecenaz; Tuncer, Temel Engin (Elsevier BV, 2018-08-01) In wireless sensor networks, node locations are required for many applications. Usually, anchors with known positions are employed for localization. Sensor positions can be estimated more efficiently by using mobile anchors (MAs). Finding the best MA trajectory is an important problem in this context. Various path planning algorithms are proposed to localize as many sensors as possible by following the shortest path with minimum number of anchors. In this paper, path planning algorithms for MA assisted loca...
Improving search result clustering by integrating semantic information from Wikipedia Çallı, Çağatay; Üçoluk, Göktürk; Şehitoğlu, Onur Tolga; Department of Computer Engineering (2010) Suffix Tree Clustering (STC) is a search result clustering (SRC) algorithm focused on generating overlapping clusters with meaningful labels in linear time. It showed the feasibility of SRC but in time, subsequent studies introduced description-first algorithms that generate better labels and achieve higher precision. Still, STC remained as the fastest SRC algorithm and there appeared studies concerned with different problems of STC. In this thesis, semantic relations between cluster labels and documents ar...
Sparse Attack Construction and State Estimation in the Smart Grid: Centralized and Distributed Models Ozay, Mete; Esnaola, Inaki; Yarman Vural, Fatoş Tunay; Kulkarni, Sanjeev R.; Poor, H. Vincent (Institute of Electrical and Electronics Engineers (IEEE), 2013-07-01) New methods that exploit sparse structures arising in smart grid networks are proposed for the state estimation problem when data injection attacks are present. First, construction strategies for unobservable sparse data injection attacks on power grids are proposed for an attacker with access to all network information and nodes. Specifically, novel formulations for the optimization problem that provide a flexible design of the trade-off between performance and false alarm are proposed. In addition, the ce...

Citation Formats

F. Semiz and F. Polat, “Incremental multi-agent path finding,” FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, pp. 220–233, 2021, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/70204.