This is the C implementation of Bi-Objective A* (BOA*), New Approach to Multi-Objective A* with dimensionality reduction (NAMOA*dr), and Bi-Objective Dijkstra (BOD). BOA* and NAMOA*dr computes a Pareto frontier containing paths from a given initial node to a given goal node on a given graph with two cost functions. BOD, instead, completes a Pareto frontier containing paths to every node of the graph from a given source node. More details in the following paper:
The implementation contained in this package assumes the graph is explicitly given.
The map files are stored in a separate file that you can download from here.
Compile using make
.
To run a single problem use ./boa [graph_file] [start_node] [goal_node]
for BOA*, ./namoadr [graph_file] [start_node] [goal_node]
or ./bod [graph_file] [start_node]
, for BOD. For example: ./boa Maps/NY-road-d.txt 1 500
.
The NAMOA*dr code can use the M3 algorithm for op-pruning. To enable this feature, define the M3 macro in include.h.