PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment

Details PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment

2011-06-30

arxiv.org/abs/1107.0041v1

Journal Of Artificial Intelligence Research, Volume 21, pages 631-670, 2004

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1373

We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A* algorithm (PHA*) for solving this problem. PHA* expands all the mandatory nodes that A* would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA* is presented as a two-level algorithm, such that its high level, A*, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming that the mandatory nodes of A* are known in advance. We then generalize our algorithm to the multi-agent case, where a number of cooperative agents are designed to solve the problem. Specifically, we provide an experimental implementation for such a system. It should be noted that the problem addressed here is not a navigation problem, but rather a problem of finding the shortest path between two points for future usage.

Affiliated with

Also associated with

No associations

Rating

PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-479997