# Graph search with a high number of actions

I have implemented A* to reach a goal state from a start state. My state is position X,Y, angle and others state variable. I have a number of actions. What I call actions is : A* on a grid has 4/8 actions (straight, right, left, back).

My character has a lot of different actions. I started with 20 possible actions which will lead to different future possible positions. with my implementation of A* it is working fine and I found a solution.

Now, I want to do the same thing but with my real number of actions. Which is around 1000... If I run my algorithm it may take forever...

This figure shows my problem :

The first red node is the start position. The green is the goal. When A* will expand my children. I will have 1000 children nodes (note: the nodes are in a kind of same region the light blue envelope)). But then I have 1000 nodes to study and which can be extented by 1000 children each... and so on. So the number can be really huge.

Does anybody have a good idea to deal with this kind of high number of actions in a A* ? Finding a good heuristic won't be enough I guess cause too many possibilities. Maybe using this light region ? Any ideas ?

Thanks. Let me know, If it is unclear or need more explanations.

• I'm unsure if I'm interpreting your picture correctly. What are the 1000 different actions? Are these different ways of your character moving? Commented Oct 9, 2015 at 22:48
• If all of those 1000 x 1000 children don't overlap (if you really do have millions or billions of possible states) then graph search (including A*) may not help much. Try to collapse similar states together, or use a hierarchical approach, or use a continuous approach instead of a discrete (graph-based) search. Commented Oct 10, 2015 at 1:16
• My character has a foot at a state 0, then 1000 different position are reachable from this state. (X,Y,Z,theta). So, the character has 1000 possible posistion where he can place his next feet. @amitp Thanks for your blog I love it and it helps me a lot. What do you mean by hierachical approach ? I think it can be interesting because of course I will prefer the state which are close to the goal or with a good angle. Thanks Commented Oct 10, 2015 at 18:52
• @Snoopyjackson I haven't worked with the hierarchical approaches myself but I think you'd first use A* or other algorithm to find roughly how to get to your goal (maybe each light red envelope would be one node), and then you'd go back and make a detailed path with something like foot placement. Commented Oct 10, 2015 at 21:47
• Also are you sure you are not ending "out of memory"? 1000 x 1000 at each step is bad big O notation Commented May 10, 2016 at 9:34

This is indeed a common and open problem in robotics and ai. When the search space is becomming too large, consider to use stochastic approaches. For planning or path finding, Rapidly Exploring Random Trees (RRT) are a promising method to efficiently find asymptotically optimal solutions.

The basic idea is to start at some initial configuration (i.e. foot on ground), randomly sample free space (i.e. possible foot positions), choose the closest sampled configuration (i.e. smallest movement needed to get to a certain foot position) and add that to your sequence of actions (i.e. foot movement from start to green).

Alternatively, you can use genetic algorithms in order to gradually approach a good solution. Some example.

If your grid contains so many nodes, One solution to avoid a freeze up on your pathfinding would be to switch to a different map representation, such as a hierarchical map, a quad tree, or navigation meshes that uses less nodes in order to speed up your search.

Another solution that could considerably improve performance would be to get rid of the closed list data structure and instead use an integer, lets say runID, to determine if a node is on the closed list. Lets assume that each node had an integer, called closedID, where we would compare that value to the runID as a way to check if it is on the closed list. If runID == closedID, then we can assume that the node is on the closed list. this could also be done with the open list when checking if a node is inside it (It won't replace the whole open list data structure, obviously). the runID would be incremented everytime you did a new search.

Another performance improvement would be to use manhattan distance instead of euclidean distance (assuming you are using it) for the heuristic. Using the sqrt() function for euclidean distance on large maps is expensive.

• THanks for you answer. I am using the euclidian distance. I will try with the manhattan. I will take a look into the different map representation but I dont really know if it is possible in my case. Commented Oct 10, 2015 at 18:58
• I have to disagree about sqrt — (1) sqrt is fairly fast, and (2) making the heuristic match the movement will save a lot more cycles processing nodes than you're paying in the cost of the sqrt function. Commented Oct 10, 2015 at 19:25
• Hmmm ok. Depending on the heuristic the computation time can change a lot right ? So I need to find the best heuristic possible. Will it be fast even with my 1000 children expansion (few min can be ok)? The character is not suppose to move very far but just few meters Commented Oct 10, 2015 at 19:33

Your problem is still open, in the sense there is so much research about optimizing pathfinding and reducing its time complexity (however there is much advancement if positions are constrained in euclidean space: so travelling cost is equal to distance), I don't know the details of your game, but I think you don't need to be 100% precise, if you have to play with foot positions I may argue a more viable solution is to just take random positions as long as those positions will end up closer to goal, then when you are close enough to your goal enable precise pathfinding in order to search for a local position.

You can even develop a strategy (the same a player would do), in a sense that you choose euristics that will move foots to predetermined locations (in example 2 vertical lines) from wich you know you can incrementally adjust nodes in the path, effectively I think your problem resembles me more Inverse Kinematics than pathfinding. If you need further delucidations just ask in comments.

In example, if you are able to reach a state such that your foots are along a line, and starting location and goal location are simmetric to that line, you then just need to know that you have to do the same moves you used to reach that line, but you have to mirror back that moves (you halve the distance of computations, wich turns in much lesser time because O is not linear)

Another possible approach, just reduce granularity of your coordinates when you are far from goal (in example instead of having 10 different states for X, just use 3/4 different states for it).

And as all algorithms, just quickly discard branches in your search that are clearly wrong or too distant, some simple heuristic will suffice.

In example, If I'm correct your are examining possible moves, wich means there will always be a move that will bring your foot back in its previous position, just discard branches for that moves.