Collaborative Search for Multi-goal Pathfinding in Ubiquitous Environments

Abstract : Multi-goal pathfinding (MGPF) is a problem of searching for a path between an origin and a destination, which allows a set of goals to be satisfied. We are interested in MGPF in ubiquitous environments that are composed of cyber, physical and social (CPS) entities from connected objects, to sensors and to people. Our approach aims at exploiting data from various resources such as CPS entities and the Web to solve MGPF. However, accessing resources creates overheads – specifically latency affecting the efficiency of the approach. In this paper, we present a collaborative multi-agent search model that addresses the latency problem. The model handles the process of accessing resources such that agents are not blocked while data from resources are being processed and transferred. Agents search concurrently and collaboratively on different parts of the search space. The model exploits the knowledge and structure of the search space to distribute the work among agents and to create an agent network facilitating agent communications as well as separating the search from the communications. To evaluate our model, we apply it in uniform cost search, creating a collaborative uniform cost algorithm. We compare it to the original algorithm. Experiments are conducted on search spaces of various sizes and structures. In most cases, collaborative uniform cost is shown to run significantly faster and scale better in function of latency as well as graph size.
Type de document :
Communication dans un congrès
Multiagent System Technologies: 15th German Conference, MATES 2017, Aug 2017, Leipzig, Germany. Springer International Publishing, Lecture Notes in Computer Science, volume 10413, pp 72-88, 〈10.1007/978-3-319-64798-2_5〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-01575624
Contributeur : Florent Breuil <>
Soumis le : lundi 21 août 2017 - 12:00:29
Dernière modification le : jeudi 11 janvier 2018 - 06:20:36

Identifiants

Citation

Oudom Kem, Flavien Balbo, Antoine Zimmermann. Collaborative Search for Multi-goal Pathfinding in Ubiquitous Environments. Multiagent System Technologies: 15th German Conference, MATES 2017, Aug 2017, Leipzig, Germany. Springer International Publishing, Lecture Notes in Computer Science, volume 10413, pp 72-88, 〈10.1007/978-3-319-64798-2_5〉. 〈emse-01575624〉

Partager

Métriques

Consultations de la notice

44