Hierarchical D ∗ algorithm with materialization of costs for robot path planning

Hierarchical D∗ algorithm with materialization of costs for robot path planning Daniel Cagigas Department of Computer Architecture and Technology, Higher Technical School of Computer Science, University of Seville, Av. Reina Mercedes s/n, 41012 Sevilla, Spain Abstract In this paper a new hierarchical extension of the D∗ algorithm for robot path planning is introduced. The hierarchical D∗ algorithm uses a down-top strategy and a set of precalculated paths (materialization of path costs) in order to improve performance. This on-line path planning algorithm allows optimality and specially lower computational time. H-Graphs (hierarchical graphs) are modified and adapted to support on-line path planning with materialization of costs and multiple hierarchical levels. Traditional on-line robot path planning focused in horizontal spaces is also extended to vertical and interbuilding spaces. Some experimental results are showed and compared to other path planning algorithms. Keywords: Path planning; Hierarchical search; D∗ algorithm; Mobile robots 1. Introduction Abstractions like graphs are useful to arrange and model information and they are very used by humans. Graphs are also widely used in mobile robotics to abstract environments [1]. Most of the mobile robot systems move into reduced environments where maps usually do not have more than a few hundreds of nodes. However, sometimes the path planner of a mobile robot must face large and structured environments where traditional branch &bound or genetic algorithms may not be efficient enough. Therefore, a plain graph information must be arranged in order to reduce complexity and gain efficiency and clarity. A hierarchical decomposition is necessary and H-Graphs (hierarchical graphs) are a very suitable choice. Hierarchical search reduces complexity of operations and can lead to important improvements when is applied to mobile robots [2]. In fact, hierarchies of abstraction can reduce exponential complexity problems to linear complexity [3]. This is important because, for example, A∗algorithm (widely used in robot path planning) has O(n2) time complexity and O(bd) space complexity, where “n” is the number of nodes, “b” is the branching factor and “d” depth level reached in a search. A hierarchical path planner is supported by a hierarchy of abstractions representing different views of a robot environment (i.e. a hierarchical map). Paths are obtained using a refinement process through the hierarchy of abstractions in order to obtain a path1free of obstacles. There may be also a reconstruction process that link partial paths obtained after refinement. Several references can be found in the bibliography. Thus, in [4] the problem of finding good abstraction hierarchies is analysed. In [5] a hierarchical multilevel discretization and a wave front expansion algorithm are used together to solve a robot motion planning problem. In [6,7] the trade off of using abstraction hierarchies is studied and analysed. In [8] a hierarchical path planning algorithm is proposed to plan a collision free path for mobile robots and robot manipulators. In [9,10] the concept of H-Graph (hierarchical graph) is described and applied to mobile robot path planning. On-line path planning refers to problems where robots must replan their initial paths because their abstract model of an environment (map) has been updated. This usually happens when an unknown obstacle is found. Branch & Bound algorithms in dynamic environments are based on RTA∗–LRTA∗[11], Dynora [12] and specially D∗[13] algorithms. The first three are real-time algorithms that combine execution and calculation cycles. They are not path length or time optimal algorithms and are constrained by computational time limitations. Genetic algorithms are an alternative path planning technique applied usually to metric maps. They provide flexibility in dynamic environments. Examples can be found in [14–16]. The newest strategies combine genetic and branch & bound algorithms. Thus, branch & bound algorithms are used to generate an initial population of paths for a genetic algorithm or regenerate it when an obstacle is found (see [17]). There are also some few on-line hierarchical robot path planners. For example, in [18] a two level hierarchical abstract map is used to speed up the problem of intercepting a moving object. Hierarchical robot path planners almost always use two hierarchical levels to model an environment. Little attention has been given to mobile robot systems with more than two hierarchical abstract levels. Moreover, maps usually represent a continuous horizontal space. Mobile robot path planning may involve two floors of a building or even several floors of different buildings. In this work, H-Graphs and the D∗algorithm are adapted to on-line and interbuilding path planning. Thus, the main contribution of this work is to convert the D∗algorithm into a hierarchical algorithm that uses precalculatedpaths(materializationofcosts).ThisimprovescomputationaltimeperformanceoftheD∗algorithmin large search spaces (including three dimension spaces), and therefore allows to obtain paths in a faster and accuracy way than traditional hierarchical path planning. The method proposed help for instance, to solve autonomous online robot navigation problems in large and/or complex indoor environments such as buildings. In some robot path planning modules, computer time availability may be limited due to real time embedded systems used. Until now on-line robot path planning systems have been usually designed for continuous and not complex environments, where quality and availability of paths obtained, were not a major problem. InSection2theH-Graphmodelproposedisdescribed.Section3describesthehierarchicalpathplannerproposed. A previous description of the D∗algorithm fundamentals are also commented. In Section 4experimental results obtained are analysed and compared to other algorithms. Finally, in Section 5some conclusions are pointed out. 2. Map model TheH-Graphproposedisasequenceofhierarchicallevels.ThesequenceisL={L0,L 1,L 2,...,L D}.Thedepth of the hierarchy is D. The “root level” is L0and it represents the highest abstract description of an environment. 1It will be used path or trajectory either. On the contrary, LDcontains the most detailed description of an environment. For example, it may contain the internal structure of a room in a building. In each level Li(0 ≤i≤D) there is a graph Gi=(Ni,A i,C i,W i,T i), where Niis a set of nodes, Aiis a set of arcs, Ciis a set of Cartesian coordinates for Ni,Wiis a set of weights for Aiand Tiis a set of precalculated paths associated to Ni. The union of graphs G0,G 1,G 2,...,G Dis a graphG=(N, A, C, W, T )whereN=N0∪N1∪...∪ND,A=A0∪A1∪...∪AD,C=C0∪C1∪...∪CD, W=W0∪W1∪...∪WD,T=T0∪T1∪...∪TD. An arc a(nJ,n K,w H)∈Ais defined by three elements nJ,n K,w H, where nJ,n K∈N,nJ= nKand wH∈W. A Cartesian coordinate cI∈Cis defined by (x, y), where x, y ∈N. A weight wI∈Wis real number (wI∈R). Some nodes can represent a cluster (subset) of nodes in a deeper abstraction level of the hierarchy. These nodes are called submap nodes and the submap node set contained in Nis called SN (SN ⊂N). There are some functions/methods associated to a node nJ∈Gj(0 ≤j≤D). The dot notation is used: •map →nJ.map =nK, where nJ∈Lj,nK∈Lk,j=k+1(0<j≤D, 0≤k≤D) and nJ⊂nKin Lk. Namely, it indicates in which node is nJincluded in an upper level of the hierarchy. It is said that nKsubmap (cluster or subset) of nJ. •depth →nJ.depth =x, where nJ∈Lx(0 ≤x≤D). Namely, it returns the level of the hierarchy where nJ belongs. Nodes are also classified in four classes: end nodes,cross nodes,submap nodes (cluster nodes) and bridge nodes. End nodes are starting or goal points that a robot path planner can select. Cross nodes represent subtargets that indicate turns or crossroads. Bridge nodes are nodes that connect a submap to a “parent” submap. The bridge node subsetcontained inNis calledBN. Formally,nI∈Giis abridge node(i.e. nI∈BN ⊂N)if thereis anodenJ∈Gj and an arc aI(nI,n J,w X)∈A, where i=j+1. The concept of bridge node leads to a new function/method: •get bridge nodes →nI.get bridge nodes =BNI⊆BN, where nI∈N,nI.depth < D and BNIsatisfies that ∀nx∈BNI,n x.map =nI. Namely, if nIis a submap, it obtains its bridge node set included in the next deeper level of the hierarchy. Bridge nodes are divided in two classes: horizontal bridge nodes and vertical bridge nodes. Horizontal bridge nodes follow the definition given before. Vertical bridge nodes are almost equal to horizontal bridge nodes but conceptually they connect two submaps that represent two floors in a building. In fact, elevator entrances are modelled as vertical bridge nodes in G. These nodes allow path planning between different floors of a building or even between floors of different buildings. Arcs (A) are non-directed: a mobile robot can navigate between two points (nodes) in both ways. An important difference from other H-Graph models is that here arcs do not contain other arcs in a deeper abstraction level of the hierarchy. Cartesian coordinates (C) are attributes associated to every node. They are used in the heuristic function of the path planner. Weights (W) are attributes associated to each arc and indicate the cost of traversing an arc. They are used by the cost function of the path planning algorithm and represent a length in metres. A path is defined as a succession of nodes. The whole set of paths contained in an H-Graph is called P. Formally, a path PI∈Pof length Lis defined by PI=(n0,n 1,n 2,...,n L), where n0,n 1,...,n L∈Nand ∃a0 (n0,n 1,w (0,1)),a 1(n1,n 2,w (1,2)),...,a L−1(nL−1,n L,w (L−1,L))∈A. A path PIhas three attributes/methods: •cost →PI.cost =x, where x∈R. It gets or assigns a path cost to PI. •length →PI.length =L+1, where L∈N,PI∈Pand PI=(n0,n 1,n 2,...,n L). It returns the path length of PI. •index →PI.index(J)=nJ, where nJ∈PI=(n0,n 1,...,n J,...,n L), nJ∈N,PI∈P,L+1=PI.length, 0≤J≤L. Namely, it returns the node of a path in position J. Each submap node nI∈Ni⊂N(0 ≤i<D) has its own precalculated path set PPSnI∈Ti⊂T(0 ≤i<D). Thus, a new method/function associated to a submap node nIcan be defined: •pre path →nI.pre path(nX,n Y)=PZ, where nX,n Y∈N,PZ=(nX,n X+1,n X+2,...,n Y−2,n Y−1,n Y), PZ∈PPSnI⊂P. Namely, a node nIreturns a path PZbetween nodes nXand nYwhether it has an attached precalculated path set PPSnIthat contains PZ. Nodes nXand nYthat define a precalculated path will be usually bridge nodes. If a node nIis not a submap node or it does not contain the required path, the method/function returns NULL. Precalculated paths in PPSnIare optimal-length paths and are off-line calculated. They are grouped in three classes: (1) Paths that link two bridge nodes inside nI. (2) Paths that link the bridge nodes of nI(nI.get bridge nodes) with the bridge nodes of its “parent” submap ((nI.map).get bridge nodes). (3) Paths that link “brother” submaps contained in nI. Two submap nodes nX,n Y∈Nare “brother” submaps contained in nIif nX.map =nY.map =nI. Namely, they are “brother” submaps if they have the same “parent” submap in the previous level of the hierarchy. Precalculated paths avoid recalculating several subpaths in a hierarchical search process. This is called materialization of costs [19]. On one hand, materialization of cost requires extra storage space for paths and costs and off-line path calculation [2]. On the other hand, it can guarantee optimality in a classic refinement hierarchical search method. Materialization of costs saves computational time too because it avoids refinement of nodes in deeper abstraction levels of the hierarchy. Extra store space and off-line path calculation are not serious drawbacks for a robot computer embedded system when working in static and well known environments such us offices, shops, industrial buildings, etc. Furthermore, the map model is highly flexible and easily adaptable. If a building map has to be updated, the intrinsic modularity of H-Graphs makes easy a partial path recalculation. Depending on the path planning module requirements, some precalculated paths or path classes may be even added or removed from the H-Graph. This last point implies a variation of the concept of materialization of costs mentioned in [19]. It could be defined as partial materialization of cost. 3. Path planning 3.1. D∗algorithm The D∗algorithm was first introduced by Stentz (see [13]). It defines and represents a dynamic or on-line version of the A∗algorithm. A∗algorithms are widely used in off-line path planning and robot motion planning. The D∗is path length optimal algorithm and saves a lot of computational time when comparing with brute-force methods. AD∗algorithm restarts the general search process of an A∗algorithm when an obstacle is detected. This is equivalent to find a “broken” arc Abin an initial path Piof a graph. Piis a time or length optimal path between an starting node Nsand a goal node Ng. Arc Abis defined by two nodes: Nc(current node), which represents the current robot position, and Nn(next node), which represents the next robot’s movement/destination. Nodes {Ns,N g,N candNn}∈N. Every node connected to the current node Nc, except Nn, is used to generate a new partial solution path set. Each new path Pnew from the new path set is added to the D∗OPEN LIST. The OPEN LIST contains a set of partial solution paths that are expanded until Ngis reached. Thus, a first path/node expansion implies to generate new partial solution paths Pnew composed of nodes included in P∗ i=(Ns,...,N c)⊂Piand Fig. 1. D∗replanning example: scheme A shows an initial path Pi.Ncis the current node and Abthe ’broken’ arc. In Scheme B nodes from OPEN LIST are expanded until another node Nx∈Piis reached. The rest of partial solution paths have a greater fvalue. This scheme represents the first algorithm end condition. Scheme C shows the final replanned path. the set of neighbour nodes connected to Nc. Formally, a path Pnew =P∗ i∪Nk, where ∃Ak=a(Nc,N k,W (c,k)), Ak= Ab,Ak∈Aand Nk∈N. Arc Abis ignored and can not be a part of any solution. The whole search process ends when: (1) Nnor another node Nxincluded in the original path Piis found and the rest of partial paths (solutions) included in the OPEN LIST have a higher fvalue. f=g+h, where gis the accumulated path cost and his the heuristic value that estimates path cost from Ncto Ng(see Fig. 1). Usually, function fimplements the Euclidean distance. (2) The goal node Ngis reached and the rest of partial paths have a higher fvalue. This is equivalent to a brute-force method and represents the worst case. (3) The OPEN LIST is empty. This means that there are no solutions without Ab. 3.2. Hierarchical path planning The general search process is similar to D∗. The “broken” arc Abconnected to the current node Ncis first erased from the H-Graph. Nodes connected to Ncare added to an OPEN LIST and then expanded until the goal node Ng is reached. Nodes Ngand Ncare supposed to be end, bridge or cross nodes (i.e. everything except submap nodes). Node processing in MAIN PROCEDURE is divided into four parts. Firstand fourth partsimplement thesamesubprocesses includedin D∗. Ifa newcandidatenode forexpansionNa isin the initialpath Pinitial, then currentpath Pcurrent is completedusing the samenodes included inPinitial, startingin Naand finishing in Ng(lines 12 to 15). Fourth part just expands Na, that is to say, generates new partial paths joining Pcurrent and Naneighbours nodes (lines 37–40). This last subprocess is detailed in D∗NODE EXPANSION procedure. Second and third parts deal with bridge nodes and submap nodes respectively. Here materialization of costs (precalculated paths) are used to link submaps through their bridge nodes or used to substitute submap nodes by their precalculated paths. MAIN PROCEDURE: D∗HIERARCHICAL PATH PLANNING (Node Nc, Node Ng, Arc Ab, Path Pinitial): 1: {Begin variable declaration}: 2: Node Na,N aux; 3: Path Pcurrent,P new; 4: Path Set Open List; 5: {End variable declaration.} 6: Pcurrent =(Nc); 7: Pcurrent.cost =0; 8: Open List =(Pcurrent); 9: while (Open List = NULL)do 10: Pcurrent =GET BEST PATH(Open List); 11: Na=Pcurrent.index(Pcurrent.length −1); 12: if (Na∈Pinitial)then 13: {The current partial path has intersected the initial path.} 14: Pnew =COMPLETE PATH(Pcurrent,N a,P initial); 15: PROCESS SOLUTION(Pnew); 16: else if (Na∈BN ⊂N)then 17: {Bridge nodes expansion is processed separately.} 18: if (Na.map = Ng.map)then 19: {Node expansion using precalculated paths (materialization of costs).} 20: HIERARCHICAL D∗NODE EXPANSION (Pcurrent,N a,P initial, Open List); 21: else 22: {Both nodes are included in the same submap.} 23: Pnew =(Na.map).pre paths(Na,N g); 24: if (Pnew = NULL) then 25: {There is a precalculated path between Naand Ng.} 26: Pcurrent =Pcurrent ∪Pnew; 27: Pcurrent.cost =Pcurrent.cost +Pnew.cost; 28: PROCESS SOLUTION(Pnew); 29: else 30: D∗NODE EXPANSION (Pcurrent,Na,Ab,Open List); 31: end if 32: end if 33: else if (Na∈SN ⊂N)then 34: {Submap nodes expansion is processed separately too.} 35: {Narepresents another subgraph in a deeper abstract level of the hierarchy. Precalculated paths (materialization of costs) are used to avoid refining paths that cross Na.} 36: D∗SUBMAP NODE EXPANSION (Pcurrent,Na,Open List); 37: else 38: {D∗normal node expansion.} 39: D∗NODE EXPANSION (Pcurrent,Na,Ab,Open List); 40: end if 41: endwhile 42: return BEST SOLUTION(); There are some subprocedures in MAIN PROCEDURE that are not detailed due to their simplicity. •GET BEST PATH (line 10). It returns and deletes the best path from a list of partial paths (Open List). The best path is the path that has the lower f=g+hvalue, that is to say, the lower cost. •COMPLETE PATH (line 14). It has three arguments: a partial solution path Pcurrent, a complete solution path Pinitial and a common node Naof both paths. Returns a new path composed of nodes from Pcurrent and nodes from Pinitial that start in Naand finish in goal node Ng. •PROCESS SOLUTION (line 15). It manages a hidden global variable which contains the best current solution Psolution. If this global variable was empty, then this subprocedure just assigns to Psolution the new solution path. If Psolution was not empty and the new solution path has a lower cost than Psolution, then it is assigned to Psolution the new solution path. •BEST SOLUTION (line 42). It returns the path contained in Psolution.IfPsolution has not any value assigned, thenit returnsNULL (thereisnot anypossiblesolution path).This subprocessexpandssubmap nodesofPsolution. It is used a similar process to D∗SUBMAP NODE EXPANSION subprocedure. The D∗NODE EXPANSION subprocedure is a key part in a D∗algorithm. First, it adds to the Open List new paths composed of nodes from the current path Pcurrent and nodes connected to the last node Naof Pcurrent. Nodes connected through a “broken” arc Abare avoided. Second, it continues the A∗search tree expansion. D∗NODE EXPANSION (Path Pcurrent, Node Na, Arc Ab, Path Set Open List): {Begin local variable declaration:} Path Pnew; Arc Ai; Node Ni; {End local variable declaration.} for all (Ai=a(Na,N i,w (a,i))∈A, Ai= Ab,Ni∈N)do if (Ni== Ng)then {The goal node Nghas been found:} Pnew =Pcurrent ∪Ni; Pnew.cost =Pnew.cost +w(a,i); PROCESS SOLUTION(Pnew); else if (Pnew.cost +w(a,i)<(BEST SOLUTION()).cost)then Pnew =Pcurrent ∪Ni; Pnew.cost =Pnew.cost +w(a,i); Open List =Open List ∪Pnew; end if end for The D∗SUBMAP NODE EXPANSION subprocedure expands submap nodes. This means that a submap node Nain a path is substituted by precalculated paths that cross Nain a deeper abstract level of the hierarchy. This may be viewed as a node unrolling. See scheme in Fig. 2. There is the possibility that precalculated paths include submapnodestoo.Thisdoesnotaffectthegeneralpathsearchprocess.However,finalsolutionpathshaveto“unroll” submap nodes. Subprocedure BEST SOLUTION in MAIN PROCEDURE performs a recursive process similar to D∗SUBMAP NODE EXPANSION before it returns a solution path. Fig. 2. Submap node expansion. A path Pcurrent ={Na−2,N a−1,N a}generates three new equivalent paths. Each new path Pnew substitutes submap node Naby a precalculated path stored in Na. D∗SUBMAP NODE EXPANSION (Path Pcurrent, Node Na, Path Set Open List): 1: {Begin local variable declaration:} 2: Node Na−1,Nj,Nk,Nh,Nlast; 3: Path Paux; 4: {End local variable declaration.} 5: Na−1=Pcurrent.index(Pcurrent.length −2); 6: Nk⇐Nk∈BN /∃a(Na−1,N k,w (a−1,k))∈Aand Nk.map =Na; 7: for all (Nj∈Na.get bridge nodes, Nj= Nk)do 8: Paux =Na.pre paths(Nk,N j); 9: Nlast =Paux.index(Paux.length −1); 10: Nh⇐Nh∈N/∃a(Nlast,N h,w (last,h))∈Aand Nh.map =Na.map =Na−1.map; 11: {In Pcurrent the last node (Na∈SN) is substituted by a refined path (Paux) that crosses that node in a deeper abstract level. It is also added the next node (Nh) that follows to Na.} 12: Pnew =(Pcurrent −Na)∪Paux ∪Nh; 13: Pnew.cost =Pcurrent.cost +Paux.cost +w(last,h); 14: Open List =Open List ∪Pnew; 15: end for The HIERARCHICAL D∗NODE EXPANSION subprocedure is another key part in the hierarchical D∗ algorithm. It implements the linkage process between different submap nodes and abstract levels. Submap nodes are linked through their bridge nodes. The same hierarchical levels (and submap nodes) included in the initial path Pinitial have to be again traversed again but nodes in between may be different. The subprocedure is divided in three steps. First step finds the next submap node Nsubmap that has to be reached. Second step finds the submap node Nsubmap pre paths that stores the precalculated paths necessaries to make the linkage process. Third step joins current path Pcurrent through its last bridge node Nawith bridge nodes of Nsubmap. See examples in Fig. 3. HIERARCHICAL D∗NODE EXPANSION (Path Pcurrent, Node Na, Path Pinitial, Path Set Open List): 1: {Begin local variable declaration:} 2: Node Nsubmap,N aux,N submap pre paths; 3: Path Paux; 4: int ind =0; 5: {End local variable declaration.} 6: {First step: get the next submap (Nsubmap) that the current partial solution path (i.e. Pcurrent) has to reach.} 7: Naux =Pinitial.index(ind); 8: while (Naux ∈ BN and Naux.map = Na.map)do 9: ind =ind +1; 10: Naux =Pinitial.index(ind); 11: end while 12: {Naux is a bridge node, “brother” of Nain the original path (Pinitial). Now it must be localized the next bridge node after Naux included in Pinitial. It will indicate the next submap traversed in Pinitial:} 13: repeat 14: ind =ind +1; 15: Naux =Pinitial.index(ind); 16: until (Naux ∈ BN) 17: Nsubmap =Naux.map; 18: {Second step: get the submap node (Nsubmap pre paths) that stores the precalculated paths that link Na(i.e. last node of Pcurrent) and the bridge nodes of Nsubmap (i.e. next submap to reach).} 19: if ((Na.map).map == Nsubmap)then 20: {The linkage process is made from Nato bridge nodes included in the “parent” submap of Na.map:} 21: Nsubmap pre paths =Na.map; 22: else if ((Nsubmap.map)== Na)then 23: {Opposite case. The linkage process is made from Nato bridge nodes included in a “children” submap of Na.map:} 24: Nsubmap pre paths =Nsubmap; 25: else 26: {Na.map and Nsubmap are “brother” submaps. Precalculated paths are stored in their “parent” submap:} 27: Nsubmap pre paths =Nsubmap.map; 28: {The sentence Nsubmap pre paths =(Na.map).map; is valid too:} 29: end if 30: {Third step: linkage process. New partial solution paths are obtained joining Pcurrent to a set of precalculated paths contained in Nsubmap pre paths.} Fig. 6. Hospital results. Lindicates total path cost (length) and Tindicates total computational time. close to results achieved with D∗algorithm in HPP cases. Results vary depending on the map because they depend strongly on graph structures. In Fig. 7 (results in the industrial buildings map) it can be noted some type of overhead. The computational time (T) with hierarchical D∗algorithm without materialization of costs is higher than in D∗and Hill Climbing Fig. 7. Industrial Buildings results. Lindicates total path cost (length) and Tindicates total computational time. Fig. 8. Headquarters building results. Lindicates total path cost (length) and Tindicates total computational time. algorithms in HPP and VPP experiments. A low node density in each floor (nodes per floor) and a low number of nodes involve in a path are determinant. Hierarchical algorithms perform more operations due to the H-Graphs complexity. Hierarchical path planning is useless and materialization of costs not very effective when replanned pathsarecontainedinasinglesubmap(nodecluster)inthedeepesthierarchicallevelofaH-Graph.Thisisequivalent Fig. 9. Airport results. Lindicates total path cost (length) and Tindicates total computational time. Fig. 10. Airport results. Genetic algorithms are included. Computational time is quite large when comparing with the rest of algorithms. to find a path in a plain graph and implies to execute always D∗NODE EXPANSION subprocedure in main procedure D∗HIERARCHICAL PATH PLANNING (line 39) (see Section 3.2). Path length (L) results using D∗with prunes algorithm are always above D∗. Its computational time is often the highest. On the contrary, using a dynamic hill climbing algorithm, computational time reductions can reach up to 50% when comparing with D∗. However, there are results that show computational time increments of more than 35% and quality of solutions obtained (sum of path lengths) is usually worse. Algorithms and path search strategies are very sensitive to map structures and local minimums. An example can be viewed in Fig. 7 where the hierarchical D∗algorithm without materialization of costs shows worse results than D∗algorithm in VPP and IPP cases. Nevertheless, the hierarchical D∗algorithm with materialization of costs, always has lower computational costs than D∗and path lengths (L) are similar. Thus, materialization of costs can help to prevent some negative side effects of pure hierarchical search. 5. Conclusions The contribution of this paper is: (1) A new version of the D∗algorithm for robot path planning that uses a hierarchical map and materialization of costs. (2) An H-Graph model G=(N, A, C, W, T ) suitable for on-line hierarchical path planning. The H-Graph model proposed allows efficient robot on-line path planning and an easy information management. (3) Extend on-line hierarchical path planning with materialization of costs to H-Graphs with several hierarchical levels (more than two). (4) Extend traditional on-line hierarchical path planning to vertical path planning and interbuilding path planning. Some other conclusions that can be drawn from this work: (1) Experimental results demonstrate the utility of the model proposed in some practical cases. The method shows better results in large scale graphs and a significant node cluster (submap) density. (2) The model proposed may be adapted to real-time robot path planning. Calculation and execution cycles can be intercalated in the same manner as the RTA∗algorithm does. Materialization of costs (precalculated paths) may help to improve real-time algorithms performance. References [1] J.C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1990. [2] J.A. Fernandez, J. Gonzalez, Multi-Hierarchical Representation of Large-Scale Space, Kluwert Academic Plublishers, 2001. [3] R.E. Korf, Planning as search: a quantitative approach, Artif. Intell. 1 (33) (1987) 65–88. [4] C.A. Knoblock, Learning abstraction hierarchies for problem solving, in: T. Dietterich, W. Swartout (Eds.), Proceedings of the Eighth National Conference on Artificial Intelligence, AAAI Press, Menlo Park, California, (1990) 923–928. [5] G. Conte, R. Zulli, Hierarchical path planning in a multi-robot environment with a simple navigation function, IEEE Trans. Syst., Man Cybernet. 25 (4) (1995) 651–654. [6] R.C. Holte, C. Drummond, M.B. Perez, Searching with abstractions: a unifying framework and new high-performance algorithm, in: Morgan-Kaufman (Ed.), Proceedings of the 10th Canadian Conference on Artificial Intelligence, (1994) pp. 263–270. [7] R.C. Holte, M.B. Perez, R.M. Zimmer, A.J. MacDonald, The tradeoff between speed and optimality in hierarchical search, Tech. rep., School of Information Technology and Engineering. University of Ottawa. Canada (1995). [8] Woong Keun Hyun, Il Hong Suh, A hierarchical collision-free path planning algorithm for robotics, Proceedings of the 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems 95, Human Robot Interaction and Cooperative Robots’, vol. 2, (1995) pp. 448–495. [9] J.A. Fernandez, J. Gonzalez, Hierarchical graph search for mobile robot path planning, Int. IEEE Conf. Robot. Automat. (ICRA’98), Leuven, Belgium, (1998) pp. 656–661. [10] J.A. Fernandez, J. Gonzalez, Multihierarchical graph search, IEEE Trans. Patt. Anal. Mach. Intell. 24 (1) (2002) 103–113. [11] R.E. Korf, Real-time heuristic search, Artif. Intell. 41–42 (1990) 189–211. [12] B. Hamidzadeh, S. Shekhar, Dynora II: a real-time planning algorithm, J. Artif. Intell. Tools (Special Issue on Real-Time AI) 2 (1) (1993) 93–115. [13] A. Stentz, Optimal and efficient path planning for partially-known environments, in: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’94), vol. 4, (1994) pp. 3310–3317. [14] I. Ashiru, C. Czarnecki, T. Routen, Characteristics of a genetic based approach to path planning for mobile robots, J. Network Comput. Appl. 19 (1996) 149–169. [15] J.M.Ahuactzin,E.-G.Talbi,P.Bessiere,E.Mazer,Usinggeneticalgorithmsforrobotmotionplanning,in:Proceedingsofthe10thEuropean Conference on Artificial Intelligence, (1992) 671–675. [16] K. Sugihara, J. Smith, Genetic algorithms for adaptative planning of path and trajectory of a mobile robot in 2D terrains, IEICE Trans. Informat. Syst. E82-D (1) (1999) 309–317. [17] H.Kanoh,A.Kashiwazaki,L.T.H.Bui,S.Nishihara,N.Kato, Real-timerouteselectionusinggeneticalgorithmsforcarnavigationsystems, in: Proceedings of the IEEE International Conference on Intelligent Vehicles, (1998) pp. 207–212. [18] T. Sasaki, F. Chimura, M. Tokoro, The trailblazer search with a hierarchical abstract map, in: Proceedings of the fourteenth International Joint Conference on Artificial Intelligence, Montreal, Canada, (1995) pp. 259–265. [19] Ning Jing, Yun-Wu Huang, Elke A. Rundensteiner, Hierarchical encoded path views for path query processing: an optimal model and its performance evaluation, IEEE Trans. Knowledge Data Eng. 10 (3) (1998) 409–432.