1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

The problem is known as the Canadian Traveler Problem.

$\endgroup$
3
$\begingroup$

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:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.