search

citiususc / hipster

Hipster4j is a lightweight and powerful heuristic search library for Java and Android. It contains common, fully customizable algorithms such as Dijkstra, A* (A-Star), DFS, BFS, Bellman-Ford and more.
http://hipster4j.github.io
Apache License 2.0
326 stars 89 forks source link

Implementation of the multiobjective algorithm NAMOA*? #169

Open FrankS101 opened 8 years ago

FrankS101 commented 8 years ago

Hi!

I was wondering if you would be interested in having the multiobjective heuristic search algorithm NAMOA* in your library? The algorithm from Martins and Santos that you have is basically a multiobjective version of Dijkstra's algorithm and it does not use any heuristic information.

NAMOA* is the extension of A* to the multiobjective case, keeping all its formal properties, with the difference that expands labels instead of nodes.

As a remark, Martin's algorithm is several orders of magnitude slower than NAMOA* for difficult problems and could be considered deprecated. NAMOA* is not the state-of-the-art either, but a much faster algorithm than Martin's.

Cheers!

pablormier commented 8 years ago

Hi Frank,

Thanks for the suggestion. Indeed, the Martin's MO algorithm is very näive and its performance is far from the performance of other state-of-the-art techniques. It would be very interesting to have an implementation of NAMOA* in Hipster4j. Do you dare to contribute to the library by making an implementation of the algorithm by yourself :+1: ?

Cheers!

FrankS101 commented 8 years ago

Hi Pablo,

It would be a pleasure to do it. I don't have much free time at the moment but I'll do my best to contribute with an implementation of the algorithm. I think I can start from Martin's algorithm as a base. Is your implementation biobjective or multiobjective? I mean, in biobjective problems are you also using the multiobjective algorithm or a more efficient biobjective version? What data structures are used to keep the OPEN labels and the labels already explored?

Cheers!

pablormier commented 8 years ago

Hi @FrankS101,

Cool to hear that!. We know that free time is precious, and we really appreciate your interest in contributing. The current implementation is a naive multiobjective (not just bi-objective), and we do not consider any kind of performance improvement for the special case of a bi-objective optimization. If you have any ideas to improve the current version of the algorithm or some prototype implementation of the NAMOA, we'd happy to know!. I will take a look to the details of NAMOA\ to see how can it fit in the library. We're aware that sometimes, due to some limitations and constraints in the design of the library, some algorithms are specially hard to fit, but implementing new algorithms is also a good way to improve the current design of Hipster4j. Feel free to discuss any kind of problem/limitation/doubt you have.

Thanks again!