Locally Constrained Shortest Paths and an Application in Mission Planning
Gregory Angelides, Andy Bartlett, André Berger, Amy Nicole Langville, Zhilin Li · ACM Southeast Regional Conference · 2006
We consider a generalization of the constrained shortest path problem, in which we forbid certain pairs of edges to appear consecutively on a feasible path. This problem has applications in robotics and optimal mission planning. We propose a dynamical programming heuristic for this problem and show computational results of an application in routing an aircraft through hostile space.