Exploratory Digraph Navigation Using A

1 Exploratory Digraph Navigation (EDN)

1.1 Exploratory Digraph Navigation problems

Imagine a mobile robot navigating in a physical world W whose representation is a directed graph (digraph) G R as sketched on Figure 1. Dotted lines on the figure represents data not available in the robot's internal map G, also called currently known graph [Felner et al., 2004], of the world at planning time. G R nG represents space not explored yet. From its current position, the robot wants to reach a goal position with minimal effort. While planning its path to the goal on G, it realizes that it essentially has two choices: using a known (safe) path, which may be quite long, or trying to find a shortcut thanks to places whose knowledge is incomplete (think of rooms containing doors not yet opened). However, taking a shortcut is risky since the expected shortcut may actually be a dead end, forcing the robot to turn back and replan its path. The said shortcut may also actually be longer than the safe path. Depending on its internal state (battery level, mission, . . . ), the robot may want to privilege the safe path or hope for luck and try an exploratory path which may lead to a decrease of traveled distance relative to the safe path while increasing the robot's knowledge of its environment.

The typical use of Exploratory Navigation is together with robotic Simultaneous Localization And Mapping (SLAM) where a robot models its environment as a graph [Choset and Nagatani, 2001; Bosse et al., 2004] or as an occupancy grid [Elfes, 1989] (where each pixel can be considered as a vertex connected to its neighbors if space is traversable). Other problems related to graph theory such as the Traveling Salesman's Problem or routing problems in changing networks (where a set of packets must travel in a network without knowledge of all the routers) may also benefit from EDN. In these problems, the computational cost (algorithm execution time) associated to planning is small but not necessarily negligible compared to the navigational cost (energy used or distance physically traveled summed on each move until destination is reached) associated to navigation and exploration.

� This research was supported by a DGA-MRIS scholarship

The navigating agent should take advantage of both charted and uncharted territory during path planning and navigation, whence the name "exploratory navigation". At the heart of EDN is a trade-off between safety guaranteed by exploitation of existing knowledge and short and long term efficiency obtained through exploration of uncharted territory, described for example by Argamon-Engelson et al. [1998].

1.2 Definitions

Let G R be a graph made of a set of vertices V R and a set of edges E R � V R �V R . Let G be a subgraph of G R . Its set of vertices is V and its set of edges E � V � V. In addition to these vertices and edges, called internal vertices and explored edges respectively, G also has boundary vertices and unexplored edges. Unexplored edges are edges whose origin is in V but whose destination is unknown. Formally, the set of unexplored edges is U � V �V R and the set of boundary vertices is B � V. Boundary vertices are vertices which possess at least one unexplored outgoing edge: B = fv 2 V; 9e 2 U; 9v 0 2 V R ; e = (v; v 0 )g. The boundary state of these vertices is known at planning time. From the definition follows that G = G R , U = ; or B = ;. V[B , V R and E[U , E R in general since some vertices and edges of G R may be missing (not yet discovered) in G.

We define Exploratory Digraph Navigation (EDN) as the problem of physically reaching a known destination F 2 G from a known origin O 2 G with minimal navigational cost and decent computational cost. Knowledge about G R can only be acquired by physically traversing yet unexplored space, modeling it as vertices and edges and adding these to G. G R is thus the theoretical limit of G when all available space has been explored.

1.3 What Exploratory Digraph Navigation is not

To our knowledge, EDN has never been formulated as such. However, a number of close problems have already been formulated. Most of them are still open as of 2014.

The Canadian Traveler Problem (CTP) [Bar-Noy and Schieber, 1991; Karger and Nikolova, 2007] and the Stochastic Shortest Path Problem with Recourse (SSPPR) [Polychronopoulos and Tsitsiklis, 1996] are concerned with graphs where some edge traversal costs may be unknown (edges may not even exist) at planning time. However, the edge traversal cost is unknown but the extremities of explored and unexplored edges are still known, which is not true for unexplored edges in EDN. D* and D*Lite [Stentz, 1995; Koenig et al., 2004; Koenig and Likhachev, 2005] are known approximate CTP/SSPPR solvers used for mobile robot planning. EDN can solve navigation problems on graphs G with unknown edge costs.

EDN is a generalization of graph exploration [Betke, 1991; Smirnov et al., 1996; Awerbuch et al., 1999; Panaite and Pelc, 1999; Dessmark and Pelc, 2004] since increasing the knowledge of G relative to G R is not mandatory in EDN but any EDN solver should be able to perform exploration at least when O and F initially belong to different components of G.

The shortest path between O and F in a partially unknown environment is provably computed by PHA* [Felner et al., 2004] for future use at the expense of immediate navigational cost. EDN is a navigation problem aiming at reaching F with minimum navigational cost. As a side effect, a reusable path from O to F is found which hopefully exhibits a low (but not necessarily minimal) navigational cost. As opposed to the approach of Argamon-Engelson et al. [1998], EDN does not require the whole graph to be considered for each planning step and only considers exploration reducing the navigational cost to the goal (immediate reward).

1.4 Exploratory Digraph Navigation as a stochastic problem

EDN can be treated stochastically (stochastic edge or vertex traversal cost). The study of pathfinding on graphs with stochastic properties, pioneered notably by Loui [1983] is an active field of research, notably with the Markov Decision Process formulation [Puterman, 1994]. EDN can conform to the formalism of stochastic graphs if every boundary vertex is connected to every other boundary vertex or directly to F with virtual edges whose traversal costs are described by probability distributions. The resulting problem can then be solved using a utility criterion [Loui, 1983] or other techniques out of scope of this paper. However, the choice of the probability distribution for each virtual edge is not trivial notably due to destinations of unexplored edges possibly already belonging to G (unexplored loops). We therefore prefer a non-stochastic approach with a single number instead of a probability distribution to represent the length of virtual edges. Our approach of EDN nonetheless shares with a recent approach of the stochastic shortest path problem by Trevizan and Veloso [2014] its tunable search horizon and penalization of intermediary goal states.

1.5 Our contribution : the EDNA* algorithm

We propose the EDNA* (for Exploratory Digraph Navigation with A*) algorithm for exploratory navigation using (possibly) incomplete digraphs. EDNA* is a generalization of A* [Hart et al., 1968] which considers shortcut hypotheses and the risk associated to them during A* expansion through a new degree of freedom. EDNA* can also be used for (goaldirected) exploration.

2 Describing the EDNA* algorithm

2.1 Notations

Let O0 be the starting position of the navigating agent. On with n > 0 is the position of the navigating agent after the n th run of EDNA*. O is always the starting position of the current run. We need the hypothesis that G R is static (it does not change during the experiments) for the theoretical proofs. SLAM experiments not reported here show that EDNA* may also work on dynamically changing graphs though.

A path is said to be admissible in a graph if it has the lowest navigational cost amongst all possible paths. Multiple paths can be admissible. 8(X;Y) 2 V 2 , let D(X;Y) be the (noncommutative) navigational cost from X to Y following an admissible path on G. G can carry arbitrary per-vertex and peredge traversal costs. If no path exists from X to Y, we take the convention that D(X; Y ) = 1.

EDNA*, like A*, requires an admissible but not necessarily consistent heuristic H [Dechter and Pearl, 1985] estimating the distance between two vertices. For a given vertex X 2 V, the value of the heuristic is written H(X; F; G), abridged to H(X) if unambiguous. The admissibility constraint (H never overestimates navigational costs) writes 8(X;Y) 2 V 2 ; H (X; Y; G) � D(X; Y ). When not mentioned otherwise, the R 2 metric space with H (X; F; G) = j jF � X j j (L2 norm) is used since it is the most common space in pathplanning applications.

It is not possible to add a shortcut discovery strategy to A* by modifying H for two reasons. First, taking a shortcut is risky so that H should be increased, which in turn is in conflict with the admissibility constraint on H. Second, a boundary vertex can be found on an admissible path, in which case there is no reason for penalizing it. For these reasons, EDNA* defines a second heuristic, R, the shortcut risk heuristic, on boundary vertices. R estimates the navigational cost of a shortcut while taking into account the risk that this cost was underestimated. Given the origin O of an EDNA* planning step and Z 2 B, the value of the heuristic writes R(O; F; Z; G). We insist on the fact that R does not replace H, even on boundary vertices where it is used to add information to H. R(O; F; Z; G) is abridged to R(O; Z) or R(Z) if there is no contextual ambiguity. There is no constraint on R (it can be negative or even infinite) even though we will see that there is no interest in having R(O; F; Z; G) < D(O; Z) +H(Z; F; G). The value of R relative to D(O; Z) +H(Z; F; G) determines how reluctant the navigating agent is to try and discover shortcuts.

Finally, we define an EDNA* run as the combination of a planning phase, purely computational, where a path to some vertex X 2 V (not necessarily F) is computed on G, and of a plan execution (or navigation) phase, purely navigational, where the agent physically navigates on W from its current position to the position x 2 W corresponding to X 2 G R while updating its current position on G. When at X, if X , F then X 2 B and the agent takes the "most promising" unexplored edge simultaneously on x and X and follows it until it reaches another vertex. We embed the concept of "most promising" or "best" edge into R by saying that for each boundary vertex, its R value is computed with the best edge in mind. For instance, the best edge may be the one whose angular difference with the goal vertex F in a metric space is the best amongst all unexplored edges on X. The most promising edge can also be chosen randomly, possibly resulting in higher navigational costs on average.

2.2 Planning with EDNA* (algorithm 1)

Like A* [Hart et al., 1968], EDNA* planning has two phases. The first one is a vertex expansion phase where vertices X are considered in order of increasing expected navigational cost �(X) = D(O; X) + H(X; F) and starting with O. The priority queue used to store vertices and their navigational cost (X; �(X)), also known as open set, is called Q. If H is not consistent, a list S (called closed set) of already encountered vertices is maintained since vertices can be encountered again with a lower �. In the second phase, an actual path is computed starting at F or Z 2 B and going back to O. The interested reader will report to open-source implementations of A* for details and implementation of the second phase. EDNA* has the same algorithmic complexity as A*. Planning is done on G and does not imply any movement inW.

2.3 Properties of the EDNA* planning algorithm

At the end of the algorithm, EDNA* returns a path to F or to a boundary vertex Z from which exploration must take place. If no path from O to F exists on G and there is no boundary vertex accessible, the algorithm can't find a path. If no path exists from O to F and there is at least one boundary vertex, the algorithm will always give the shortest path leading to the boundary vertex Z with the lowest R(O; F; Z) encountered during expansion. It will thus perform similarly to Agent-Centered A* [Smirnov et al., 1996] if

Algorithm 1 Planning with EDNA*

Input: O, F, G, H : X !H(X; F; G) Input: R : Z ! R(O; F; Z; G) dest ;; best distance 1; Q (O; �(O)); S ; while Q , ; do pop (X; �(X)) fromQ; S (X; �(X)) if �(X) > best distance then break //EDNA* early stopping criterion if X = F then dest F; best distance �(F) break //traditional A* stopping criterion if X 2 B then if R(O; F; X) � best distance then dest X; best distance R(O; F; X) for all neighbors T of X do compute �(T) if not ( (T 2 S and �(T) � �(T)S) or (T 2 Q and �(T) � �(T)Q) � then Q (T; �(T))

8 Z 2 B; R(O; F; Z; G) < = D(O; Z) +H(Z; F; G). EDNA* is a greedy algorithm since the path choice is always optimized for the current origin O. Finally, EDNA* always expands less vertices than A* during one planning phase since vertices expanded by EDNA* would be expanded by A* but the early stopping criterion based on R (see algorithm) may stop the algorithm before the whole A* search space has been expanded. However, F may not be reached in one run, so that EDNA*'s search space may end up being bigger than A*'s.

2.4 Navigation with EDNA* (algorithm 2)

In order for the agent to actually move in the world, a navigation algorithm compatible with the EDN paradigm is required. The simple algorithm 2 performs the navigation task while being independent of the underlying planner (here EDNA*). Physically following a path or exploring an edge means that the navigating agent simultaneously moves inW, which incurs a navigational cost, and updates its current position on G. Vertex recognition and map update must be handled by a separate algorithm, such as those used for topological SLAM (see [Bosse et al., 2004] for example). Figure 2 shows an example of EDNA* reducing the navigational cost compared to A* thanks to a shortcut.

2.5 Convergence proof and exploration variant

Let e and emax be the amount of explored edges in the component around O0 of G and G R respectively.

Theorem 1 (Navigation success and upper bound). If G R is strongly connected, EDNA* will always lead the navigating agent to F 2 G R from any O0 2 G R . A maximum of 1 + (emax � e) EDNA* navigation runs will be necessary.

Corollary 1 (Complete graph exploration). If F is unreachable from O0 because both vertices belong to a different component in G R , at most (emax � e) EDNA* navigation runs will lead to exploration of the whole component containing

Algorithm 2 Navigation with EDNA*

Input: W, O, F, G, H : X !H(X; F; G) Input: R : Z ! R(O; F; Z; G) n = 0;On O // origin while On , F do call EDNA* Planning(On; F; G; H; R) ! Returns path to On+1 physically follow path fromOn to On+1 //takes time n n + 1 if On = F then break //successfully reached F physically explore best edge E to reach a vertex On+1 n n + 1, insert E in G //new edge while (On < G) do insert On in G //new vertex if On < B then break //dead end physically explore best edge E to reach On+1 n n + 1, insert E in G //new edge

O0 before returning an error. The 1 + (emax � e) bound is tight.

Sketch of the proof : an EDNA* run either leads to F, returns an error or registers at least one new edge in G, so that at most (emax � e) runs would lead to e = emax . As EDNA* is exactly A* when the graph is completely known (G = G R ), a last EDNA* run on G R will lead to F if reachable or return an error if not reachable, but after having discovered the component containing O0 (otherwise, there would be a boundary vertex which EDNA* would target). The bound is tight considering a chain of vertices connected in G R but not in G.

Using F < G R , corollary 1 can be used to achieve complete exploration of an unknown graph prioritizing a specific position or direction. The position of F will be used to bias shortcut discovery, but as the vertex can't be reached, the whole subgraph around O0 will be explored, starting with the part closest to F.

2.6 Theoretical study of the R heuristic

DG R indicates that the navigational cost is computed on G R instead of G. From a theoretical point of view, five cases are particularly interesting regarding the R heuristic:

1. early stopping to privilege exploration: 8 Z 2 B; R(O; F; Z; G) < = D(O; Z) + H (Z; F; G) 2. optimal case: 8 Z 2 B; R(O; F; Z; G) < = D(O; Z) + H (Z; F; G) and 8 X 2 G;H(X; F; G) = DG R (X; F) 3. optimal improvement over uninformed A* on G: 8 Z 2 B; R(O; F; Z; G) = D(O; Z) + DG R (Z; F) 4. improvement over uninformed A* on G: 8 Z 2 B; R(O; F; Z; G) > D(O; Z) + DG R (Z; F) 5. EDNA* reduced to A* on G: 8 Z 2 B; R(O; F; Z; G) !1

Case 1 sees the expansion phase stopping at the first boundary vertex encountered due to the early stopping criterion. If 8X 2 G;H(X) = 0 (Dijkstra's algorithm), with F unreachable (or no F at all) and with unitary traversal costs, this would result in the greedy algorithm Nearest Neighbor (NN) [Koenig and Smirnov, 1996]. NN's penalty in terms of traversed edges on a non-directed graph during exploration relative to traversed edges if the graph was known is only worst-case logarithmic in the number of edges [Megow et al., 2011]. Bounds for algorithms operating on digraphs are still an open problem [Megow et al., 2011] but due to its greedy nature, we expect EDNA* to reach a competitive ratio of n�1 with n the number of vertices in G R [F¨orster and Wattenhofer, 2012]. EDNA*'s relocation strategy (using known edges to travel from a newly completed vertex to a boundary vertex) is however not specifically optimized for exploration tasks compared to that of Albers and Henzinger [1997] or Fleischer and Trippen [2005].

In case 2, H is fully informed, so that A* on G R would only expand vertices directly on admissible paths (optimal search space). It is possible to prove that EDNA* on G with such heuristic choices will follow a path admissible on G R using navigation on known parts of the path and exploration on yet to be discovered parts. Case 3 yields the same result in terms of path followed but with a bigger search space.

Case 4 results in EDNA* on G always overestimating the navigational cost of shortcuts (in case 5, all shortcuts are considered of infinite cost). This means that the stopping criterion can only be triggered if an exploratory path's navigational cost is actually lower than all non-exploratory ones.

However, it may not be triggered if a path is found from O to F with a cost between DG R (O; F) and the lowest R. This case is the one that we try to achieve in practice, the hard part being that setting an upper bound on the navigational cost of a specific shortcut is not always possible.

For a given problem which EDNA* must solve, if bounds can be given on D(Z; F) for every possibly interesting boundary vertex Z, then bounds can be given on EDNA*'s suboptimality in terms of navigational cost: the worst case detour relative to A* on G R in the fourth case is the estimated D(O; Z) + D(Z; F) minus the actual one.

3 Experiments

3.1 Finding a reference algorithm

Both EDNA* and D* (Lite) [Stentz, 1995; Koenig et al., 2004; Koenig and Likhachev, 2005] can provide suboptimal (greedy) navigation in a static CTP/SSPPR situation, such as on grid-like graphs. D* and its variants use a free-space assumption ("unexplored space is traversable") resulting in a systematical underestimation of the navigational cost. As a consequence, transforming unexplored vertices to vertices with all edges unblocked makes EDNA* with R = 0 follow the D*Lite path but without D*Lite's search space optimization. D* (Lite) can't work on digraphs where nothing is known about yet unexplored vertices.

It is possible to use PHA* [Felner et al., 2004] for navigation by stopping the algorithm when F is reached for the first time (Felner et al. do not mention this possibility). In this situation, the path returned would be either the A* path on G (infinitely overestimating the length of shortcuts, obtainable with EDNA* and R ! 1) or that of iterated AgentCentered A* [Smirnov et al., 1996] (obtainable with EDNA* and R = 0). Not stopping PHA* early would result in a lot of physical movements increasing the navigational cost and unnecessary for a navigation task. PHA* can't balance physical exploration of unknown parts and navigation on known parts even though it ends up using both.

More generally, EDNA* uses the exploration risk as a degree of freedom which none of the above algorithms does. EWP [Argamon-Engelson et al., 1998] considers balancing exploration and navigation, but no algorithm to do it during planning is described. As a consequence, each iteration of EWP must compute the navigational cost from the current position to any v1 2 B (algorithm not explained in the article) and estimate the cost from it to any v2 2 B which is orders of magnitude more compute-intensive than our approach. When using exploration, EWP navigates to the best v1 from where it must reach the best v2 using exploration even though another v 2 V is reached while going from v1 to v2. As a consequence, the navigational cost from O0 to F ends up being always higher than that of our approach in the same situation.

Our objective is to demonstrate shortcut discovery i.e. EDNA* reaching F from O0 with a lower navigational cost than a non-exploratory strategy such as A*, whence the comparison of EDNA* to A*. Map knowledge improvement due to adding newly discovered zones to G is not evaluated but is expected to strongly reinforce the interest of EDNA* since future traversals can benefit from currently discovered shortcuts, dead ends and loops.

3.2 A simple choice of R for experiments

We chose to use a risk heuristic R(O; F; Z; G) = D(O; Z) + � (1 � �:cos(�)) H(Z; F; G) in an Euclidean space with the L2 norm as H. � is the angle between an edge going out from Z and the vector from Z to F, � is a parameter to describe an angular penalty and � is a parameter to describe the total penalty in the sense that if � = 0, � describes by how much a shortcut's navigational cost is overestimated relative to H(Z; F; G). (� � 1; � = 0) for instance gives the first case of the previous section. This proposal of heuristic is inspired by the way humans actually find shortcuts in an unknown environment (possible shortcuts are edges which go in the right direction and would potentially save a lot of time or distance). For a high enough risk factor �, R should fall in case 4 of the previous section. It should be noted that R does not take advantage of the planarity of a graph.

3.3 Benchmark protocol

Let NA� and NEDNA� be the navigational cost fromO0 to F using A* and EDNA* on a graph G. The navigational cost change from A* to EDNA* on G is NG = NA��NEDNA� NA� . A �0:1 change means that if the cost following the A* path is 100 units, the one following the EDNA* path is 100 � 10. Similarly, a computational cost change CG is computed using the number of vertices visited during the expansion phase of the algorithms which reflects execution time.

nG R = 200 random planar digraphs G R with about 9 000 vertices and 12 500 dual-way edges each are generated, with square-shaped possibly-overlapping (SSPO) obstacles of varying size. Generating graphs allows control over obstacle shapes and obstacle density. G R intends to mimic road networks or Generalized Voronoi Graphs [Choset and Nagatani, 2001] while being more labyrinthine and misleading in order to test the worst-case behavior of EDNA*. G is obtained by removing a fraction � of the edges of G R to create SSPO unexplored zones. In each experiment attempt, G is created from G R and O0 and F are randomly chosen. Due to the edge removal procedure, O0 and F may belong to different components of G, leading to A* being unable to find a path but EDNA* still finding one. Such cases represent more than 50% and up to 95% (high �) of all experiment attempts. They are eliminated as giving EDNA* an infinite navigational advantage over A*, thus strongly favoring A* with respect to EDNA*. In these cases, a new experiment attempt is done until a successful experiment occurs, where A* finds a path from O0 to F. Successful experiments are accumulated until an informative experiment occurs, where NG , 0 (NG = 0 means R is not used). There are ns successful experiments including the last one which is informative. On each G R , 10 000 informative experiments are done, uniformly sampling 100 values in [1; 9] for � and 100 values in [10%; 50%] for �.

The estimators used for each (�; �) to retrieve the average navigational and computational cost changes plotted on figures 3 and 4 are ¯N = 1 P G R � 1 P G NG � and

n GR : ns : ¯C = 1 n GR : P G R � 1 ns : P G CG � . Both estimators average on all G R the (poor) average on all successful experiments on a given G R . Arithmetically averaging changes is intuitive but highly unfavorable to EDNA* since a 0:9 degradation (navigational cost multiplied by 1:9) balances a 0:9 improvement (navigational cost divided by 10) of EDNA* over A*.

� � 0:25 was experimentally observed to give EDNA* the best navigational improvements over A*. Tests were also carried on 8-way connected grid-like graphs like that of Figure 2 for which � � 0:125 gave better results.

3.4 Results and discussion

EDNA* vs A* navigational cost ( ¯N) comparison

Figure 3, left shows EDNA* with � > 5 always reducing ¯N compared to A* in average, demonstrating successful shortcut discovery. With � � 8, informative experiments show navigational costs divided by up to 14 when switching from A* to EDNA*. With � > 8, EDNA*'s success decreases with � because most experiments are not informative (early stopping is not triggered). The maximum performance gain of EDNA* over A* on random graphs is 3:9% with our experimental protocol unfavorable to EDNA* (since experimental results approximately follow a Gaussian distribution, the 95% confidence interval is [0:5%; 7:3%]). We observed that selection of the sole experiments where A* reaches F causes the A* shorter/EDNA* shorter limit to be biased towards high � when � increases, thus further disadvantaging EDNA*. Results on grid-like graphs (Figure 3, right) show up to 20% improvement of navigational cost of EDNA* over A*.

EDNA* vs A* computational cost ( ¯C) comparison

Figure (4, right) shows an increase from A* to EDNA* of ¯C when multiple EDNA* runs are required. This penalty for EDNA*, which exceeds 100% with low � and high � is most of the time located between 0 and 100%, especially in the high � zone (which is the interesting zone as seen in the paragraph on ¯N). Figure (4, left) shows the same result as Figure (4, right) but on a single EDNA* run where the stopping criterion allows EDNA* to always expands less space than A*. With a high � and a low �, this difference reaches 100% (EDNA* explores close to no vertices). With a low � and a high �, each run of EDNA* performs only marginally better than A* but there are less runs, so that EDNA*'s and A*'s performances are equivalent (with � = 0 or � ! 1, EDNA*

would fall back to A*). EDN's focus is on navigational cost but the figures show a computational cost comparable to that of A*, which has been proved optimal in a non-exploratory situation [Hart et al., 1968].

4 Conclusion

We present the Exploratory Digraph Navigation problem and the EDNA* algorithm to solve it. With a R heuristic sufficiently overestimating shortcut lengths, the agent using EDNA* will on average move from 3:9% to more than 20% less than using A* to reach F, with best EDNA* runs dividing the navigational cost by up to 14. Moving less leads for instance to energy savings, especially if the path is intended to be taken multiple times like in routing problems. Shortcuts, dead ends and loops found during exploration phases are stored in G. The impact of this knowledge reinforcement has yet to be evaluated. Minimizing computational cost is not the main focus of EDN problems where traversal is much slower than planning. Nonetheless, even if EDNA* tends to expand about twice as many vertices as A* during the whole navigation, it expands less per planning step which is interesting for real-time systems where single computations must terminate quickly. Moreover, if O and F are not connected on G, A* fails and an exploration algorithm has to be used. EDNA* on the contrary does not fail and automatically resorts to exploration, thus combining the navigation (A*) and the exploration algorithm. The relative amount of navigation and exploration can be tuned through R. Additional data such as metric or semantic properties or planarity could be integrated into H and R for better results.

When using an exploratory strategy, it happens that the navigating agent starts to thoroughly explore a dead end. Ideas to deal with this situation have already been formulated for exploration algorithms [Smirnov et al., 1996]. We are working on a non-stubbornness criterion which would detect this situation on the current vertex X by comparing D(O0; X) +H(X; F) to H(O0; F). Triggering this criterion would lead to an increase of R, causing EDNA* to try finding a safe path instead of hoping for a non-existing shortcut. Another possible solution to the issue would be to give the navigating agent an energy budget which would decrease with each detour while R would increase.