Return to Answer

Use D* Lite if you want AI that behaves in the way that a human might when exploring a completely new and unknown area, needing no prior knowledge of the map except for the coordinates of start and goal, and which can adapt to a changing map. This algorithm is both conceptually simpler and more efficient than the original D*, effectively obsoleting D*. It's been used in some of the Mars rovers. This algorithm eliminates the typical "omniscient", know-it-all behaviour of AIs we've all seen in games, the ones that move based on a single pre-emptive A* run on a known map.

D* Lite works on an ad hoc basis. It begins by calculating a fairly direct path between the designated goal and start points, working backward from goal to start, not yet knowing the occupancy status of those nodes along the path. It then begins to walk this path, like a pioneer.

This continues until it hits an obstacle on a node which it previously expected to walk through on its way to the goal. As a result of this mishap, it recalculates the remaining path (again backwards from goal to present position) based on the now known obstacle(s) and tries to continue stepping. Each time it find a new obstacle along its path, it recalculates as best it can based on the sum total of its current knowledge. If it follows a path to a dead-end, it will backtrack and seek new routes to goal.

P.S. "Most efficient" depends on your use case. For procedural, changing terrains and where realistic exploration is paramount, D* Lite is "most efficient".

P.P.S. Just like A*, you can also accelerate D* Lite with Jump Point Search, also mentioned here.

D* Lite if you want AI that behaves in the way that a human might when exploring a completely new and unknown area, needing no prior knowledge of the map except for the coordinates of start and goal, and which can adapt to a changing map. This algorithm is both conceptually simpler and more efficient than the original D*, effectively obsoleting D*. It's been used in some of the Mars rovers. This algorithm eliminates the typical "omniscient", know-it-all behaviour of AIs we've all seen in games, the ones that move based on a single pre-emptive A* run on a known map.

D* Lite works on an ad hoc basis. It begins by calculating a fairly direct path between the designated goal and start points, working backward from goal to start, not yet knowing the occupancy status of those nodes along the path. It then begins to walk this path, like a pioneer.

This continues until it hits an obstacle on a node which it previously expected to walk through on its way to the goal. As a result of this mishap, it recalculates the remaining path (again backwards from goal to present position) based on the now known obstacle(s) and tries to continue stepping. Each time it find a new obstacle along its path, it recalculates as best it can based on the sum total of its current knowledge. If it follows a path to a dead-end, it will backtrack and seek new routes to goal.

P.S. "Most efficient" depends on your use case. For procedural, changing terrains and where realistic exploration is paramount, D* Lite is "most efficient".

P.P.S. Just like A*, you can also accelerate D* Lite with Jump Point Search, also mentioned here.

Generalized Adaptive A* (GAA*) is good where you want a constantly moving target. I've not tried it myself but the linked paper suggests that it is faster than A* and D* Lite etc. for this purpose.

Use D* Lite if you want AI that behaves in the way that a human might when exploring a completely new and unknown area, needing no prior knowledge of the map except for the coordinates of start and goal, and which can adapt to a changing map. This algorithm is both conceptually simpler and more efficient than the original D*, effectively obsoleting D*. It's been used in some of the Mars rovers. This algorithm eliminates the typical "omniscient", know-it-all behaviour of AIs we've all seen in games, the ones that move based on a single pre-emptive A* run on a known map.

D* Lite works on an ad hoc basis. It begins by calculating a fairly direct path between the designated goal and start points, working backward from goal to start, not yet knowing the occupancy status of those nodes along the path. It then begins to walk this path, like a pioneer.

This continues until it hits an obstacle on a node which it previously expected to walk through on its way to the goal. As a result of this mishap, it recalculates the remaining path (again backwards from goal to present position) based on the now known obstacle(s) and tries to continue stepping. Each time it find a new obstacle along its path, it recalculates as best it can based on the sum total of its current knowledge. If it follows a path to a dead-end, it will backtrack and seek new routes to goal.

P.S. "Most efficient" depends on your use case. For procedural, changing terrains and where realistic A exploration is paramount, D* Lite is "most efficient".

P.P.S. Just like A*, you can also accelerate D* Lite with Jump Point Search, also mentioned here.

Use D* Lite if you want AI that behaves in the way that a human might when exploring a completely new and unknown area, needing no prior knowledge of the map except for the coordinates of start and goal, and which can adapt to a changing map. This algorithm is both conceptually simpler and more efficient than the original D*, effectively obsoleting D*. It's been used in some of the Mars rovers. This algorithm eliminates the typical "omniscient", know-it-all behaviour of AIs we've all seen in games, the ones that move based on a single pre-emptive A* run on a known map.

D* Lite works on an ad hoc basis. It begins by calculating a fairly direct path between the designated goal and start points, working backward from goal to start, not yet knowing the occupancy status of those nodes along the path. It then begins to walk this path, like a pioneer.

This continues until it hits an obstacle on a node which it previously expected to walk through on its way to the goal. As a result of this mishap, it recalculates the remaining path (again backwards from goal to present position) based on the now known obstacle(s) and tries to continue stepping. Each time it find a new obstacle along its path, it recalculates as best it can based on the sum total of its current knowledge. If it follows a path to a dead-end, it will backtrack and seek new routes to goal.

P.S. "Most efficient" depends on your use case. For procedural, changing terrains and where realistic exploration is paramount, D* Lite is "most efficient".

P.P.S. Just like A*, you can also accelerate D* Lite with Jump Point Search, also mentioned here.

Use D* Lite if you want AI that behaves in the way that a human might when exploring a completely new and unknown area, needing no prior knowledge of the map except for the coordinates of start and goal, and which can adapt to a changing map. This algorithm is both conceptually simpler and more efficient than the original D*, effectively obsoleting D*. It's been used in some of the Mars rovers. This algorithm eliminates the typical "omniscient", know-it-all behaviour of AIs we've all seen in games, the ones that move based on a single pre-emptive A* run on a known map.

D* Lite works on an ad hoc basis. It begins by calculating a fairly direct path between the designated goal and start points, working backward from goal to start, not yet knowing the occupancy status of those nodes along the path. It then begins to walk this path, like a pioneer.

This continues until it hits an obstacle on a node which it previously expected to walk through on its way to the goal. As a result of this mishap, it recalculates the remaining path (again backwards from goal to present position) based on the now known obstacle(s) and tries to continue stepping. Each time it find a new obstacle along its path, it recalculates as best it can based on the sum total of its current knowledge. If it follows a path to a dead-end, it will backtrack and seek new routes to goal.

P.S. Just like A*, you can also accelerate D* Lite with Jump Point Search, also mentioned here.

Use D* Lite if you want AI that behaves in the way that a human might when exploring a completely new and unknown area, needing no prior knowledge of the map except for the coordinates of start and goal, and which can adapt to a changing map. This algorithm is both conceptually simpler and more efficient than the original D*, effectively obsoleting D*. It's been used in some of the Mars rovers. This algorithm eliminates the typical "omniscient", know-it-all behaviour of AIs we've all seen in games, the ones that move based on a single pre-emptive A* run on a known map.

D* Lite works on an ad hoc basis. It begins by calculating a fairly direct path between the designated goal and start points, working backward from goal to start, not yet knowing the occupancy status of those nodes along the path. It then begins to walk this path, like a pioneer.

This continues until it hits an obstacle on a node which it previously expected to walk through on its way to the goal. As a result of this mishap, it recalculates the remaining path (again backwards from goal to present position) based on the now known obstacle(s) and tries to continue stepping. Each time it find a new obstacle along its path, it recalculates as best it can based on the sum total of its current knowledge. If it follows a path to a dead-end, it will backtrack and seek new routes to goal.

P.S. "Most efficient" depends on your use case. For procedural, changing terrains and where realistic A exploration is paramount, D* Lite is "most efficient".

P.P.S. Just like A*, you can also accelerate D* Lite with Jump Point Search, also mentioned here.