Incremental multi-agent path finding

2021-03-01
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.
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE

Suggestions

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...
Multimodal concept detection in broadcast media: KavTan
SOYSAL, Medeni; Alatan, Abdullah Aydın; TEKİN, Mashar; ESEN, Ersin; SARACOĞLU, Ahmet; Acar, Banu Oskay; Ozan, Ezgi Can; Ates, Tugrul K.; SEVİMLİ, Hakan; SEVİNÇ, Muge; ATIL, Ilkay; Ozkan, Savas; Arabaci, Mehmet Ali; TANKIZ, Seda; KARADENİZ, Talha; ÖNÜR, Duygu; SELÇUK, Sezin; Alatan, A. Aydin; Çiloğlu, Tolga (Springer Science and Business Media LLC, 2014-10-01)
Concept detection stands as an important problem for efficient indexing and retrieval in large video archives. In this work, the KavTan System, which performs high-level semantic classification in one of the largest TV archives of Turkey, is presented. In this system, concept detection is performed using generalized visual and audio concept detection modules that are supported by video text detection, audio keyword spotting and specialized audio-visual semantic detection components. The performance of the p...
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.
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...
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...
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.