  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.
