boost A* visitor with a custom edge weight penalty?

Question

I am playing with boost A* algorithm, started with the example found at: http://www.boost.org/doc/libs/1_37_0/libs/graph/example/astar-cities.cpp

I see that you can override its heuristics and its visitor to have some sort of custom tweaks, just that I don't quite get the concept yet for such a thing like the following, as a learning example, I'd like the algorithm to NOT pick a edge city - city, if travel time (edge weight) is greater than X, for example 100 minutes. (only if possible, if no other path is found, then that city should be chosed instead of not path found)

I tried a custom heuristic class which returns a greater time than reality, to "trick" it not to chose that city, however the problem is that with this trick, the penaltied city gets discarded, even for further interactions. (The following example explains it: B->D is discarded as a better path is found, but city D is not discarded (you see it's picked in a following iteration)

So I simplified the problem furter:

enum nodes {
    A, B, C, D, E, N
  };
  const char *name[] = {
    "A", "B", "C", "D", "E", "F"
  };
edge edge_array[] = {
    edge(A,B), edge(B,C),
    edge(C,D), edge(D,E),
    edge(B,D) // B to D is the problem here, it should be excluded
  };
cost weights[] = { // estimated travel time (mins)
    // 107, 174, 283, 71, 436
    35, 58, 94, 23, 145
  };

With this example (taking the code from original as base), I get a route:

Start vertex: A

Goal vertex: E

Shortest path from A to E: A -> B -> D -> E

Total travel time: 204.5

The problem is the B -> D path, which is such a long distance (supposing a threshold of 100, for example, that would be preferable a path like: A -> B -> C -> D -> E, this way, the distance between 2 cities is not superior to 100 (of course only if possible, if no other path, any have to be chosen)

I solved it in a suboptimal way: A custom function once adding the edge, that, (or setting manually weight) return travelTime > 100 ? travelTime * 2 : travelTime, which can be achieved for testing with:

cost weights[] = { // estimated travel time (mins)
    // 107, 174, 283, 71, 436
    (35 > 100) ? 35*2 : 35, (58 > 100) ? 58*2 : 58, (94>100) ? 94*2 : 94, 23, (145 > 100) ? 145*2 : 145
  }; // The comparisons are not needed, just there to better explain what the custom add_edge function will do.

With this method, I get the desired A -> B -> C -> D -> E, but this way, is just a hack/workaround the problem and modifies input data internally, which I think it is not the best solution.

Is there any better way to achieve this without having to manually change distances/travel time?

Answer 1

What you're trying to has nothing to do with heuristics. The A* search algorithm is breadth-first search with benefits. The heuristic is there to add a lower-bound to what the final cost will be. For a map doing street directions, straight-line distance is the perfect heuristic. The point of the heuristic is to ensure that you expand your best likely candidates before your worst likely candidates. Again, in a map sense, breadth-first search would basically circle outwards until you find your destination - whereas the heuristic makes it so that you would ooze towards your destination directly and have way fewer paths worth considering. From a different perspective - the heuristic is a function that takes the current last point in the path and the destination point and returns a cost. You cannot use it to exclude edges, as it does not know about the path. It only knows about two points.

Back to your problem. You want:

I'd like the algorithm to NOT pick a edge city - city, if travel time (edge weight) is greater than X, for example 100 minutes. (only if possible, if no other path is found, then that city should be chosed instead of not path found)

A heuristic has nothing to do with specific graph nodes or edges. It's just an estimate for the final cost and likely shouldn't be dependent on the graph itself. What you're asking for has to do with the weights. A* is all about finding minimum-weight path. If you want an edge to NOT be taken... simply up its weight!

The example you linked to has these weights:

cost weights[] = { // estimated travel time (mins)
  96, 134, 143, 65, 115, 133, 117, 116, 74, 56,
  84, 73, 69, 70, 116, 147, 173, 183, 74, 71, 124
};

You want new weights, basically:

auto new_weights = at_most(weights, 100); // I don't want to use any edges
                                          // that take 100 minutes

Which we could write thusly:

template <size_t N>
std::array<cost, N> at_most(cost (&old)[N], cost max_cost) {
    cost total = std::accumulate(old, old+N, 0.0f) * N;
    std::array<cost, N> new_weights;
    for (size_t i = 0; i < N; ++i) {
        new_weights[i] = old[i] < max_cost ? old[i] : old[i] + total;
    }
    return new_weights;
}

Basically, we just sum ALL the weights and replace all the edges that have cost larger than what you stipulated as your maximum with a new weight that is larger than taking ALL the edges. The end result of this is that if there exists a path that does not use any of the >100-weight edges, it will definitely have a lower total cost than this new path. The specific new weight we use isn't important, it just needs to be sufficiently large to guarantee the truth of the previous statement.

We do not need to change the heuristic. Just the weights.

Answer 2

I think you just wanted shortest paths here (dijkstra would be alright).

The key is to realize that you can use a custom edge_weight property map. This could be e.g. boost::property_map::transform_value_property_map<> like so:

auto my_custom_weight_map = 
    boost::make_transform_value_property_map(
            [](float w) { return w>100? 10*w : w; },
            boost::get(boost::edge_weight, g));

You see that any edge weight above 100 will be increased tenfold.

Then, you're basically already done:

    astar_search_tree(g, start, 
            distance_heuristic<mygraph_t, cost>(goal),
            boost::weight_map(my_custom_weight_map) // THIS LINE ADDED
                .predecessor_map(make_iterator_property_map(p.begin(), get(boost::vertex_index, g)))
                .distance_map(make_iterator_property_map(d.begin(), get(boost::vertex_index, g)))
                .visitor(astar_goal_visitor<vertex>(goal))
        );

And the result is:

Start vertex: A
Goal vertex: E
Shortest path from A to E: A -> B -> C -> D -> E
Total travel time: 210

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>
#include <list>

// auxiliary types
struct location {
    float y, x; // lat, long
};

typedef float cost;

// euclidean distance heuristic
template <class Graph, class CostType>
class distance_heuristic : public boost::astar_heuristic<Graph, CostType> {
  public:
    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
    distance_heuristic(Vertex goal) : m_goal(goal) {}
    CostType operator()(Vertex /*u*/) {
        return 0; // Not really needed here
    }

  private:
    Vertex m_goal;
};

struct found_goal {}; // exception for termination

// visitor that terminates when we find the goal
template <class Vertex> class astar_goal_visitor : public boost::default_astar_visitor {
  public:
    astar_goal_visitor(Vertex goal) : m_goal(goal) {}
    template <class Graph> void examine_vertex(Vertex u, Graph &/*g*/) {
        if (u == m_goal)
            throw found_goal();
    }

  private:
    Vertex m_goal;
};

int main() {
    // specify some types
    typedef boost::adjacency_list<boost::listS, boost::vecS,
            boost::undirectedS, boost::no_property,
            boost::property<boost::edge_weight_t, cost> 
        > mygraph_t;

    typedef boost::property_map<mygraph_t, boost::edge_weight_t>::type WeightMap;
    typedef mygraph_t::vertex_descriptor vertex;
    typedef mygraph_t::edge_descriptor edge_descriptor;
    typedef std::pair<int, int> edge;

    enum nodes { A, B, C, D, E, N };
    const char *name[] = { "A", "B", "C", "D", "E", "F" };
    edge edge_array[] = {
        edge(A, B), edge(B, C), edge(C, D), edge(D, E), edge(B, D) // B to D is the problem here, it should be excluded
    };
    cost weights[] = { // estimated travel time (mins)
                       // 107, 174, 283, 71, 436
                       35, 58, 94, 23, 145
    };

    unsigned int num_edges = sizeof(edge_array) / sizeof(edge);

    // create graph
    mygraph_t g(N);
    WeightMap weightmap = get(boost::edge_weight, g);
    for (std::size_t j = 0; j < num_edges; ++j) {
        edge_descriptor e;
        bool inserted;
        boost::tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
        weightmap[e] = weights[j];
    }

    // pick start/goal
    vertex start = A;
    vertex goal = E;

    std::cout << "Start vertex: " << name[start] << std::endl;
    std::cout << "Goal vertex: "  << name[goal]  << std::endl;

    std::vector<mygraph_t::vertex_descriptor> p(num_vertices(g));

    using boost::get;

    // do a real edit
    std::vector<cost> d(num_vertices(g));

    auto my_custom_weight_map = 
        boost::make_transform_value_property_map(
                [](float w) { return w>100? 10*w : w; },
                boost::get(boost::edge_weight, g));

    try {
        // call astar named parameter interface
        astar_search_tree(g, start, 
                distance_heuristic<mygraph_t, cost>(goal),
                boost::weight_map(my_custom_weight_map)
                    .predecessor_map(make_iterator_property_map(p.begin(), get(boost::vertex_index, g)))
                    .distance_map(make_iterator_property_map(d.begin(), get(boost::vertex_index, g)))
                    .visitor(astar_goal_visitor<vertex>(goal))
            );

    } catch (found_goal fg) { // found a path to the goal
        std::list<vertex> shortest_path;
        for (vertex v = goal;; v = p[v]) {
            shortest_path.push_front(v);
            if (p[v] == v)
                break;
        }

        std::cout << "Shortest path from " << name[start] << " to " << name[goal] << ": ";
        std::list<vertex>::iterator spi = shortest_path.begin();
        std::cout << name[start];

        for (++spi; spi != shortest_path.end(); ++spi)
            std::cout << " -> " << name[*spi];

        std::cout << std::endl << "Total travel time: " << d[goal] << std::endl;
        return 0;
    }

    std::cout << "Didn't find a path from " << name[start] << "to" << name[goal] << "!" << std::endl;
    return 0;
}