Optimal and Efficient Path Planning for Partially-Known ...

1 In Proceedings IEEE International Conference on Robotics and Automation, May and Efficient path Planning for Partially-Known EnvironmentsAnthony StentzThe Robotics Institute; Carnegie Mellon University; Pittsburgh, PA 15213 AbstractThe task of Planning trajectories for a mobile robot hasreceived considerable attention in the research of the work assumes the robot has a complete andaccurate model of its environment before it begins tomove; less attention has been paid to the problem ofpartially known environments. This situation occurs foran exploratory robot or one that must move to a goallocation without the benefit of a floorplan or terrain approaches plan an initial path based on knowninformation and then modify the plan locally or replan theentire path as the robot discovers obstacles with itssensors, sacrificing optimality or computational efficiencyrespectively.

2 This paper introduces a new algorithm, D*,capable of Planning paths in unknown, partially known,and changing environments in an efficient, Optimal , andcomplete IntroductionThe research literature has addressed extensively themotion Planning problem for one or more robots movingthrough a field of obstacles to a goal. Most of this workassumes that the environment is completely known beforethe robot begins its traverse (see Latombe [4] for a goodsurvey). The Optimal algorithms in this literature search astate space ( , visibility graph, grid cells) using the dis-tance transform [2] or heuristics [8] to find the lowest costpath from the robot s start state to the goal state. Cost canbe defined to be distance travelled, energy expended, timeexposed to danger, , the robot may have partial or noinformation about the environment before it begins itstraverse but is equipped with a sensor that is capable ofmeasuring the environment as it moves.

3 One approach topath Planning in this scenario is to generate a global path using the known information and then attempt to locally circumvent obstacles on the route detected bythe sensors [1]. If the route is completely obstructed, anew global path is planned. Lumelsky [7] initially assumesthe environment to be devoid of obstacles and moves therobot directly toward the goal. If an obstacle obstructs thepath, the robot moves around the perimeter until the pointon the obstacle nearest the goal is found. The robot thenproceeds to move directly toward the goal again. Pirzadeh[9] adopts a strategy whereby the robot wanders about theenvironment until it discovers the goal. The robotrepeatedly moves to the adjacent location with lowest costand increments the cost of a location each time it visits it topenalize later traverses of the same space.

4 Korf [3] usesinitial map information to estimate the cost to the goal foreach state and efficiently updates it with backtracking costsas the robot moves through the these approaches are complete, they are alsosuboptimal in the sense that they do not generate thelowest cost path given the sensor information as it isacquired and assuming all known, a priori information iscorrect. It is possible to generate Optimal behavior bycomputing an Optimal path from the known mapinformation, moving the robot along the path until either itreaches the goal or its sensors detect a discrepancybetween the map and the environment, updating the map,and then replanning a new Optimal path from the robot scurrent location to the goal. Although this brute-force,replanning approach is Optimal , it can be grosslyinefficient, particularly in expansive environments wherethe goal is far away and little map information [15] increases efficiency by using a quad-tree[13] to represent free and obstacle space, thus reducing thenumber of states to search in the Planning space.

5 Fornatural terrain, however, the map can encode robottraversability at each location ranging over a continuum,thus rendering quad-trees inappropriate or paper presents a new algorithm for generatingoptimal paths for a robot operating with a sensor and a mapof the environment. The map can be complete, empty, orcontain partial information about the environment. Forregions of the environment that are unknown, the mapmay contain approximate information, stochastic modelsfor occupancy, or even a heuristic estimates. Thealgorithm is functionally equivalent to the brute-force, Optimal replanner, but it is far more algorithm is formulated in terms of an optimalfind- path problem within a directed graph, where the arcsare labelled with cost values that can range over acontinuum.

6 The robot s sensor is able to measure arc costsin the vicinity of the robot, and the known and estimatedarc values comprise the map. Thus, the algorithm can beused for any Planning representation, including visibilitygraphs [5] and grid cell structures. The paper describesthe algorithm, illustrates its operation, presents informalproofs of its soundness, optimality, and completeness, andthen concludes with an empirical comparison of thealgorithm to the Optimal The D* AlgorithmThe name of the algorithm, D*, was chosen because itresembles A* [8], except that it isdynamic in the sensethat arc cost parameters can change during the problem-solving process. Provided that robot motion is properlycoupled to the algorithm, D* generates Optimal trajecto-ries.

7 This section begins with the definitions and notationused in the algorithm, presents the D* algorithm, andcloses with an illustration of its objective of a path planner is to move the robotfrom some location in the world to a goal location, suchthat it avoids all obstacles and minimizes a positive costmetric ( , length of the traverse). The problem spacecan be formulated as a set ofstates denoting robot loca-tions connected bydirectional arcs, each of which has anassociated cost. The robot starts at a particular state andmoves across arcs (incurring the cost of traversal) to otherstates until it reaches thegoal state, denoted by. Everystateexcept has abackpointer to a next statedenoted by. D* uses backpointers to representpaths to the goal. The cost of traversing an arc from state to state is a positive number given by thearc costfunction.

8 If does not have an arc to , then is undefined. Two states and areneighbors inthe space if or is A*, D* maintains an list of states. The list is used to propagate information about changesto the arc cost function and to calculate path costs to statesin the space. Every state has an associatedtag,such that if has never been on thelist, if is currently on the list, andGXGYbX()Y=YXcX Y,()YXcX Y,()XYcX Y,()cY X,()OPENOPENXtX()tX()NEW=XOPENtX()OPEN=X OPEN if is no longer on the list. Foreach state, D* maintains an estimate of the sum of thearc costs from to given by thepath costfunction. Given the proper conditions, this estimate isequivalent to the Optimal (minimal) cost from state to, given by the implicit function. For each stateon the list ( ,), thekey function,, is defined to be equal to the minimum ofbefore modification and all values assumed bysince was placed on the list.

9 The key functionclassifies a state on the list into one of two types:a state if, and a state if. D* uses states on the listto propagate information about path cost increases ( ,due to an increased arc cost) and states topropagate information about path cost reductions ( ,due to a reduced arc cost or new path to the goal). Thepropagation takes place through the repeated removal ofstates from the list. Each time a state is removedfrom the list, it isexpanded to pass cost changes to itsneighbors. These neighbors are in turn placed on the list to continue the on the list are sorted by their key functionvalue. The parameter is defined to be forall such that. The parameterrepresents an important threshold in D*: path costs lessthan or equal to are Optimal , and those greater than may not be Optimal .

10 The parameter is defined tobe equal to prior to most recent removal of a statefrom the list. If no states have been removed,is ordering of states denoted by is defined tobe asequence if for all such thatand for all such that. Thus, asequence defines a path of backpointers from to. Asequence is defined to bemonotonic if( and) or( and) for all suchthat. D* constructs and maintains a monotonicsequence, representing decreasing current or lower-bounded path costs, for each state that is or was on the list. Given a sequence of states, state isanancestor of state if and adescendant of all two-state functions involving the goal state, thefollowing shorthand notation is used:.Likewise, for sequences the notation is notation is used to refer to a function independentof its ()CLOSED=XOPENXXGhG X,()XGoGX,()XOPENt X()OPEN=kG X,()hG X,()hG X,()XOPENXOPENRAISEk G X,()hG X,()<LOWERkG X,()hG X,()=RAISEOPENLOWEROPENOPENOPEN kminminkX()()XtX()OPEN=kminkminkminkoldk minOPEN koldX1XN{, }bXi1+()Xi=i1i N<XiXj ij(,)1i j<N XNX1X1XN{, }tXi()CLOSED=hG Xi,()hG Xi1+,()<tXi()OPEN=kG Xi,()hG Xi1+,()<i1i N<GX{,}XOPENX1XN{, }XiXj1ijN < Xj1jiN < fX()fG X,() X{}GX{,} f () DescriptionThe D* algorithm consists primarily of two functions: and.