Path replanning in path finding algorithms

Question

I'm working on a path finding algorithm for my thesis and I've gotten to a problem I need to solve where agents can replan their path if they need/have to. For example, if an agent is traversing across a corridor and then a barrier is inserted in, the agent has to replan because his old path is invalid. Another case is if the barrier already exists and the agent has to take a longer route, but while traveling, the barrier is removed and a significantly shorter route becomes available so the agent may replan but can still continue on his old path.

I have some ideas on how to work on the first case, but I'm at a loss for where to start for the second case. Does anyone know how other path planning algorithms deal with replanning, or can point me to any resources that can help me find some direction in tackling this problem?

Answer 1

The problem is known as the Canadian Traveler Problem.

Answer 2

The problem is also knwon and heavily studied as Dynamic Vehicle Routing Problem (or On-line vehicle routing problem):

It differs from the static counterpart because:

1. Not all information relevant to the planning of the routes is known by the planner when the routing process begins;

2. Information can change after the initial routes have been constructed.

You can take a look to:

• Victor Pillaca, Michel Gendreauc, Christelle Guéreta, Andrés L. Medaglia, A review of dynamic vehicle routing problems, (2011);

• Victor Pillaca, Christelle Guéreta, Andrés L. Medaglia, Dynamic Vehicle Routing Problems: State of the art and Prospects, (2010);

• Allan Larsen's thesis: The Dynamic Vehicle Routing Problem, with some real-world applications;