Algorithm for CGF real-time route replanning in dynamic environment

Optimal route planning is central to CGF's behaviors simulation. The arc costs may change during CGF traversing through the planed route based on initial information, then the remainder of the path needs to be replanned. The D* algorithm (Dynamic A*) plan optimal route in real-time by incrementally propagating path cost changes as new information is discovered, which is suitable for route replanning in dynamic environment. An extension to D* algorithm was described that uses domain heuristic information to guide state expansion, thus reduces the number of state expansion. This extension significantly improves the efficiency of CGF's route re-planning in a dynamic environment.