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 notifications@github.com 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