Finding the Optimal Path in a Graph from Start to End with Necessary and Optional Waypoints Under a Cost Constraint

Question

I am working on a problem involving pathfinding in a weighted graph where I need to travel from a start node to an end node while considering a mix of necessary and optional waypoint nodes. The key aspects of the problem are that there exists necessary waypoints (nodes that must be visited on any valid path from the start to the end node) and optional waypoints. These optional waypoints are not strictly necessary in a valid path, but I would prefer to visit as many of them as possible. There is also a maximum cost constraint.

My goal is to find a valid path, if one exists, that satisfies the following criteria:

1. Mandatory Constraint Satisfaction: First and foremost, I need to determine if there exists any path from the start node to the end node that visits all the necessary waypoints and remains within the maximum cost constraint.
2. Optimal Optional Inclusion: If such a path exists, I then want to find a path that maximizes the number of optional waypoints visited while still satisfying the cost constraint.

Example Illustration:

• Start Node: A
• End Node: B
• Necessary Waypoints: [W1, W2]
• Optional Waypoints: [O1, O2, O3]
• Maximum Cost: C

Given this setup, I want to:

1. Find if there exists any path A -> ... -> B that visits W1 and W2 within the cost C.
2. If such a path exists, find the path that maximizes the number of nodes from [O1, O2, O3] that can be included without exceeding the cost C.

Approaches Considered:

• I have considered using Dijkstra’s algorithm for shortest paths and have found a way to find the shortest path given the start node, end node, and the necessary waypoints by modeling each state with a “waypoint memory” that contains the current waypoints visited. However, I am not sure how to extend this to the unnecessary waypoints.
• I have thought about trying an exhaustive search with backtracking but am concerned about performance due to combinatorial explosion.

My Question:

1. What algorithms or techniques would be most appropriate for this type of pathfinding problem? Ideally, it should be able to handle a large amount of unnecessary waypoints.

Any guidance on how to approach or optimize for these requirements would be highly appreciated!

Answer 1

You say you have solved the problem of including mandatory way points. Now you want to add optional waypoints. So move an optional waypoint from the optional to the mandatory list and solve. Repeat until you cannot find an optional waypoint that can be added without exceeding the cost constraint.

You comment: "I don’t see a way to find the specific 7 waypoints without checking all"

This called searching a solution space. If you want to guarantee that the absolute optimum will always be found, then you need to do an exhaustive search through the space. If you can accept an approximate solution that is often close to the perfect answer, but runs a lot faster, there are a lot of algorithms to choose from. For example, hill climbing ( AKA greedy ), simulated annealing, low rez then hi rez locally and quite a few more. That list should be enough to keep you googling for a while :-)