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, ;) -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 16.04.2015 12:16, haitam wrote:
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 -- Tiago de Paula Peixoto <tiago@skewed.de>
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@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 ? -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
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 ? * LOG ---------------------------------------------------------------------- /bin/mkdir -p '/usr/lib/python2.7/dist-packages/graph_tool/include/layout' /usr/bin/install -c -m 644 graph_arf.hh graph_sfdp.hh '/usr/lib/python2.7/dist-packages/graph_tool/include/layout' make[4]: Leaving directory `/home/htm/camp/graph-tool/src/graph/layout' make[3]: Leaving directory `/home/htm/camp/graph-tool/src/graph/layout' Making install in search make[3]: Entering directory `/home/htm/camp/graph-tool/src/graph/search' CXX graph_bfs.lo CXX graph_dfs.lo CXX graph_dijkstra.lo CXX graph_bellman_ford.lo CXX graph_astar.lo CXX graph_astar_implicit.lo CXX graph_search_bind.lo CXX graph_moastar.lo CXX graph_moastar_implicit.lo CXXLD libgraph_tool_search.la make[4]: Entering directory `/home/htm/camp/graph-tool/src/graph/search' make[4]: Nothing to be done for `install-exec-am'. /bin/mkdir -p '/usr/lib/python2.7/dist-packages/graph_tool/search' /bin/bash ../../../libtool --mode=install /usr/bin/install -c libgraph_tool_search.la '/usr/lib/python2.7/dist-packages/graph_tool/search' libtool: install: /usr/bin/install -c .libs/libgraph_tool_search.so /usr/lib/python2.7/dist-packages/graph_tool/search/libgraph_tool_search.so libtool: install: /usr/bin/install -c .libs/libgraph_tool_search.lai /usr/lib/python2.7/dist-packages/graph_tool/search/libgraph_tool_search.la libtool: finish: PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/sbin" ldconfig -n /usr/lib/python2.7/dist-packages/graph_tool/search ---------------------------------------------------------------------- Libraries have been installed in: /usr/lib/python2.7/dist-packages/graph_tool/search* PICTURE <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4026078/moastar.jpg> -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
I found the missing brick. The export to be called from "graph_search_bind.cc" ... export_moastar(); ... -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 17.04.2015 17:00, haitam wrote:
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. -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
haitam -
Tiago de Paula Peixoto