Orientdb: Is there any implementation of A* (A Star) ,D* ( D Star), Theta* ( Theta Star) , SMA* for Path Finding ?

[saeedtabrizi]

Hi
I have a question about path finding problem.
Is there any A* , D* , D* Lite , SMA* function implementations in orientdb or plan to develop them ?
Thanks
Saeed Tabrizi

[luigidellaquila]

Hi @saeedtabrizi

Right now there is only an implementation of Dijkstra algorithm, but we have plans to implement new algorithms in the near future

Thanks

Luigi

[w3aponx]

You should be able to find and use some graph algorithms in Tinkerpop
Furnace (https://github.com/tinkerpop/furnace/wiki). In theory, these
should be able to work on top of the Blueprints implementation in OrientDB.

Mario

On Fri, Apr 8, 2016 at 7:45 AM, Saeed Tabrizi [email protected]
wrote:

Hi
I have a question about path finding problem.
Is there any A* , D* , D* Lite , SMA* function implementations in orientdb
or plan to develop them ?
Thanks
Saeed Tabrizi

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub
https://github.com/orientechnologies/orientdb/issues/5957

---

Mario Cormier

[saeedtabrizi]

Dear @luigidellaquila and @w3aponx
Many thanks for reply .
I decided add some path finding functions to orientdb now .
at the first Astar function must be implement that similar implementation with the Dijkstra .
is public class OSQLFunctionAstar extends OSQLFunctionPathFinder true name for A* function ?
certainly i'm working to read Dijkstra implementation source code and test result to have a good implementation similar Dijkstra .
also i decided add an optional parameter for clearing how edge class name can be search in my implementation .
"astar(<sourceVertex>, <destinationVertex>, <weightEdgeFieldName>, [<edgeTypeClassName>], [<direction>])";
is my suggested syntax .
are you agree with this conditions ?

[luigidellaquila]

Hi @saeedtabrizi

That would be awesome! You can extend OSQLFunctionPathFinder but it's not mandatory.
You can also take a look at OSQLFunctionShortestPath, btw you can have a map as last parameter of the function, so that you can pass additional options if needed without changing the signature (see OSQLFunctionShortestPath and bindAdditionalParams() )

Please let me know if you need guidance on this

Thanks

LUigi

[saeedtabrizi]

Dear @luigidellaquila
Thanks for your reply and guide .
Just review the codes as you say . the map parameters is so ideal for me and good idea for implementing flexible parametric algorithm's , like the _limitation_ in depth, or giving 2 or more property name in FDstar or ThetaStar .
i correct the astar syntax as below :
"astar(<sourceVertex>, <destinationVertex>, <weightEdgeFieldName>, [<options>])"; // options defaults : {direction:"BOTH",edgeTypeNames:[] , parallel : false }
and i want declare FD* like this :
"fdstar(<sourceVertex>, <destinationVertex>, [<options>])"; // options defaults : {xAxisWeightFieldName : "x",yAxisWeightFieldName : "y",zAxisWeightFieldName : "z",direction:"BOTH",edgeTypeNames:[] , parallel : false }

Let me know your opinion about function syntax defintion .

Regrads
Saeed

[luigidellaquila]

Hi @saeedtabrizi

+1 for both signatures

Thanks

Luigi

[saeedtabrizi]

Hi @luigidellaquila ,
The final syntax for AStar function is :
"astar(<sourceVertex>, <destinationVertex>, <weightEdgeFieldName>, [<options>]) \n // options : {direction:\"OUT\",edgeTypeNames:[] , vertexLocationAxisNames:[] , parallel : false }";

Notes about parameters :
vertexLocationAxisNames = the axis of x,y,z or more fields in vertex to eval the Heuristic Costs . ( if pass no param it work's like dijkesrta ,if pass two param like {lat , lon} or {x , y} it uses manhatan distance and if pass more than 2 fieldname it works like FDStar) , array of string .
edgeTypeNames = the filter edgeType that would be in AStar path finding process .(if pass empty it's working with all connected edge to vertex) . array of string .
parallel : for enable paralleling . true or false
direction : direction for traversing edges (in, out, both) .

Let me know your opinion about it .
Everything works well but i want to have more test function for performance and stability . :)

Regards
Saeed

[lvca]

I like options as a JSON. @luigidellaquila do we already support it in SQL parser?

[luigidellaquila]

Hi @saeedtabrizi

It seems perfect!

@lvca yes, map params are already supported and used in shortestPath as well

Thanks

Luigi

[saeedtabrizi]

Hi @luigidellaquila
Is there any way to call orientdb user defined function ?
I want to put an optional parameter in the final syntax for enable custom Heuristic function calling .

"astar(<sourceVertex>, <destinationVertex>, <weightEdgeFieldName>, [<options>]) \n // options : {direction:\"OUT\",edgeTypeNames:[] , vertexAxisNames:[] , parallel : false , tieBreaker:true , maxDepth:99999,dFactor:1.0,customHeuristicFormula:'custom_Function_Name_here' }";

and currently how can i call a javascript or sql function in my implementation ?

 protected double getCustomHeuristicCost(final String functionName,final String[] vertextAxisNames,final OrientVertex start,final OrientVertex goal,final OrientVertex current,final OrientVertex parent,final long depth, double dFactor) {

        double heuristic = 0.0;
        // a javascript or sql function must be called here and returns a double value to heuristic 
        return heuristic;
    }

Thanks
Saeed

[luigidellaquila]

Hi @saeedtabrizi

I don't know if I got it right, but I think what you need is this:

    OFunction function = db.getMetadata().getFunctionLibrary().getFunction("functionName");
    function.execute(...);

Thanks

Luigi

[saeedtabrizi]

Hi @luigidellaquila
That's ready to use in #6002 .
I planned to add Lazy Theta Star algorithm to orientdb now . :+1:
Thanks
Saeed

[lvca]

@saeedtabrizi thanks for your PR, it looks like well done. About the Lazy Theta Star it would be a nice addition.

[saeedtabrizi]

Hi @luigidellaquila and @lvca
After the many hours , i can pull my changes commit to orientdb develop branch :D in #6019 PR

Thanks
Saeed

[luigidellaquila]

Hi @saeedtabrizi

Thank you very much, I really appreciate your efforts.
I'm checking it now

Thanks

Luigi

[luigidellaquila]

Hi @saeedtabrizi

I'm closing this issue, as the PR was merged long time ago.
For the record, I also rewrote Dijkstra function to delegate to A* (a single implementation, less moving parts, less code to maintain and less bugs in the long term ;-) )

Thank you very much!!

Luigi