Running D' First Time on Graph Initially a MarkG Open and Queue Mark all other states New a Run Process States on queue until path found or empty When edge cost cX,Y) changes Ifx is marked closed then a Update h(X a Mark x open and queue with key h(X)
Running D* First Time on Graph Initially Mark G Open and Queue Mark all other states New Run Process_States on queue until path found or empty. When edge cost c(X,Y) changes If X is marked Closed, then Update h(X) Mark X open and queue with key h(X)
Use d* to Compute Initial Path MNO NEW NEW NEW EW E G NEW NEW NEW NEW B DH K NEW NEW NEW NEW s A C F NEW NEW NEW NEW States initially tagged nEW( no cost determined yet)
Use D* to Compute Initial Path J M N O E I L G B D H K S A C F NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW States initially tagged NEW (no cost determined yet)
Use d* to Compute Initial Path OPEN List UMNO NEW NEW NEW NEW (0,G) h=0 E G NEW NEW NEW OPEN 8: if kold =h(x)then B D H K 9: for each neighbor Y of X NEW NEW NEW NEW 10: if t(Y= NEWoI 11:(b(Y=X and h(Y)th(x)+c,Y)or 12:(b()≠ X and h(Y)>hQⅩ)+c(,Y)then SA C F 13: b(Y)=X; Insert(Y, h(X)+c,m) NEW NEW NEW NEW Add goal node to the open list Process oPen list until the robot s current state is closed
Use D* to Compute Initial Path J M N O E I L G B D H K S A C F NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW OPEN NEW NEW OPEN List 1 (0,G) h = 0 8: if kold = h(X) then 9: for each neighbor Y of X: 10: if t(Y) = NEW or 11: (b(Y) = X and h(Y) ≠ h(X) + c(X,Y)) or 12: (b(Y) ≠ X and h(Y) > h(X) + c(X,Y)) then 13: b(Y) = X; Insert(Y,h(X) + c(X,Y)) Add Goal node to the OPEN list. Process OPEN list until the robot’s current state is CLOSED
Process state: New or lowered state a Remove from Open list state X with lowest k a If X is a new/lowered state, its path cost is optimal Then propagate to each neighbor Y a If Y is New, give it an initial path cost and propagate a If Y is a descendant of x, propagate any change O Else, if X can lowerYs path cost Then do so and propagate
Process_State: New or Lowered State Remove from Open list , state X with lowest k If X is a new/lowered state, its path cost is optimal! Then propagate to each neighbor Y If Y is New, give it an initial path cost and propagate. If Y is a descendant of X, propagate any change. Else, if X c an lower Y’s path cost, Then do so and propagate
Use d* to Compute Initial Path OPEN List UMNO NEW NEW NEW NEW (0,G) h=0 E G NEW NEW NEW OPEN 8: if kold =h(x)then B D H K 9: for each neighbor Y of X NEW NEW NEW NEW 10: if t(Y=NEW oI 11:(b(Y=X and h(Y)th(x)+c,Y)or 12:(b(Y)#X and hY>h(X)+c(X,Y))then SA C F 13: b(Y=x; Insert(Y, h(X)+C(X,Y)) NEW NEW NEW NEW Add new neighbors of g onto the open list Create backpointers to G
Use D* to Compute Initial Path J M N O E I L G B D H K S A C F NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW NEW OPEN NEW NEW OPEN List 1 (0,G) h = 0 8: if kold = h(X) then 9: for each neighbor Y of X: 10: if t(Y) = NEW or 11: (b(Y) = X and h(Y) ≠ h(X) + c(X,Y)) or 12: (b(Y) ≠ X and h(Y) > h(X) + c(X,Y)) then 13: b(Y) = X; Insert(Y,h(X) + c(X,Y)) Add new neighbors of G onto the OPEN list Create backpointers to G