Graph search with a high number of actions

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.