Implementation of the multiobjective algorithm NAMOA*?

[FrankS101]

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]

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 👍 ?

Cheers!

[FrankS101]

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]

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!