NEW APPROACH FOR DECENTRALIZATION OF A* Report as inadecuate




NEW APPROACH FOR DECENTRALIZATION OF A* - Download this document for free, or read online. Document in PDF available to download.

1 Computer mathematics faculty, Dept.Informatique, University of Science and Technology of Oran BP 1505, El M’Naouar, Oran, 31000 Algeria 2 UNICAEN - Université Caen Normandie

Abstract : In this paper, we propose a new approach for the decentralization of the A* algorithm called DEPA* decentralization parallel A*, which is a quick algorithm for finding the shortest path between two nodes in a large graph. The main disadvantage of the A* algorithm is that over the course instance to be processed is large and complex more resolution will be difficult in time of execution and space memory. For this, we propose an approach based on multi-agent systems that decomposes the graph into sub-graphs connecting many agents. This connection is guaranteed thanks to the characteristics of intelligent agents all computing an A* at each sub-graph in a parallel way. The initial and final states of each agent will be chosen according to well-defined heuristics. A coordinator agent resolves the conflict in the case of many final states in a sub-graph. Then, the agents interact to achieve the goal. We illustrate this approach on a grid connected by square cells.

Keywords : Agent A DEPA Grid Node Muli-Agent Systems





Author: Mohammed Chennoufi - Fatima Bendella - Maroua Bouzid -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents