Path Finding in Unknown Environment Based on Exploration Agents
Xugang Ye · 2007
Path finding is an interesting and challenging topic in the field of Artificial Intelligence. It has received extensive research attention during the last three decades. Most of the early work was focused on the geometric path finding problems in which the shortest paths connecting a set of origins and a set of goals in a geometric space populated by a finite number of previously known static polygonal obstacles are supposed to be found. Relatively recently, some researchers addressed the problem of path finding on the planetary surface. A feature of this problem is that the globally reliable prior terrain information is not available, or only partially available. Hence, the navigation decisions are highly dependent on the accurate local information dynamically and incrementally collected by the rovers themselves. Since the 1990’s several replanning algorithms have been developed for navigating a single ground mobile robot in a changing, or partially known, or unknown environment. In order to improve the efficiency and reliability, the use of multiple agents are suggested in very recent literature. Motivated by this trend, this paper aims to find efficient and effective algorithm for commanding a team of ground mobile robots to start from a single base, move in an unknown environment, and finally find the target location in a swift manner. Meanwhile, based on the acquired environmental knowledge, a path from the base to the target location is constructed such that the traveling cost (or defined as length in general sense) of this path is as small as possible. In this paper, we first study a generic single-agent exploration mechanism and its practical implementation; we then extend the mechanism into the coordination methods for multiple agents. Both the theoretical and the numerical results are presented.