Multi-Objective A-star + Vector Weight + Non-dominated Distances

Hi All,
I would like to know whether with the actual A-star, we can be able to
develop a multi-objective approach. After a brief introduction I came to
know that it is possible to have a vector weight, and customize the
different steps of the algorithm with a Visitor. Now I am wondering if:
+ the objective function (distance) can only be a scalar and not a vector ?
+ Is the algorithm (behind the scenes) bear a multi-objective
implementation, for instance for A* a tree is constructed, but for MOA*
rather an Acyclic Graph is constructed.

If not supported, I should maybe be add a new search algorithm to the set.
What is the best way to extend Graph Tool ? Do I have only to create the
graph_moastar.cc, graph_moastar.hh, graph_moastar.lo and update the Makefile
in the src/graph/search folder ?

Thank you for your attention,
:wink:

Hi All,
I would like to know whether with the actual A-star, we can be able to
develop a multi-objective approach. After a brief introduction I came to
know that it is possible to have a vector weight, and customize the
different steps of the algorithm with a Visitor. Now I am wondering if:
+ the objective function (distance) can only be a scalar and not a vector ?
+ Is the algorithm (behind the scenes) bear a multi-objective
implementation, for instance for A* a tree is constructed, but for MOA*
rather an Acyclic Graph is constructed.

Multiobjective A* with vector weights is not implemented.

If not supported, I should maybe be add a new search algorithm to the set.
What is the best way to extend Graph Tool ? Do I have only to create the
graph_moastar.cc, graph_moastar.hh, graph_moastar.lo and update the Makefile
in the src/graph/search folder ?

Yes, as well as the python code in src/graph_tool/search/__init__.py.
Just take at look at the astar code, and reproduce its structure.

Best,
tiago

Thanks for your feedback.

I have actually duplicated the astar_search while renaming the module as
moastar_search (the code is the same).
So "make install" works fine.

However when I run a simple test example I get this error:

*htm(a)htm-ub:~/camp$ ./moastar.py
Traceback (most recent call last):
  File "./moastar.py", line 47, in <module>
    heuristic=lambda v: h(v, target, pos)
  File "/usr/lib/python2.7/dist-packages/graph_tool/search/__init__.py",
line 2069, in moastar_search
    libgraph_tool_search.moastar_search(g._Graph__graph,
AttributeError: 'module' object has no attribute 'moastar_search'*

Is something missing ? Even if installation was successful ?

Even if does compile and install successfully (see the log below), the
libgraph_tool_search module does not recognize the moastar_search (see
picture below).
Just to let you know, I have clear the previous make and uninstalled
graph-tool, then restarted the operation. The new installation in
__init__.py at (/usr/lib/python2.7/dist-packages/graph_tool/search) contains
the changes I have done. such:
/__all__ = ["bfs_search", "BFSVisitor", "dfs_search", "DFSVisitor",
           "dijkstra_search", "DijkstraVisitor", "bellman_ford_search",
           "BellmanFordVisitor", "astar_search", "AStarVisitor",
           "StopSearch", "moastar_search", "MOAStarVisitor"]/

Something is missing and I am not aware of it. What do you think ?

I found the missing brick. The export to be called from
"graph_search_bind.cc"
...
export_moastar();
...

Yes, you have to be sure that the symbols are in fact exported to
python.