If you're interested in understanding STRIPS style planners then yes, it's best just to implement your own. I'm not aware of any publicly available at the moment, mostly because those working in the planning community have been focusing on post STRIPS-style planners for the past decade or so.
Just on the terminology, which might help your lit review... searching from the goal backwards is generally called "regression planning", as opposed to progression or forward planning (planning from the starting state).
Cheers,
Timkin
STRIPS planning implementation?
Quote:Original post by BrianL
The search direction itself shouldn't matter very much if you use an admissible search algorithm. At least behaviorally - the size of the space you search may vary.
May vary a *lot*, since you have to consider all actions at every step if you search forward, instead of just those actions that solve a current goal when searching backward, no? Friends of mine always suggest to do a bi-directional search and pick the first one that finds a plan, or merge the plans if they meet, but I found that the regression search / backtracking only is always faster using the optimization described above. It limits the plan-space a bit of course...
Wouldn't an informed forward search (ie A*) address the 'only consider actions which solve towards the goal' issue?
Quote:Original post by BrianL
Wouldn't an informed forward search (ie A*) address the 'only consider actions which solve towards the goal' issue?
Since the possibility space is not geometric, there isn't a really good heuristic to use that would tell the algorithm that you are "towards the goal".
Yeah. For the heuristic you would have to look at actions that solve subgoals of actions that solve subgoal of actions that solve... etc one of the current goal. You would have to plan in order to plan. A Forward search is much more of a "blind search", in the action space at least.
If performance is a concern, you should be thinking about hierarchical planners anyway rather than forwards/backwards A* :-)
Alex
Alex
Quote:Original post by Steadtler
Yeah. For the heuristic you would have to look at actions that solve subgoals of actions that solve subgoal of actions that solve... etc one of the current goal. You would have to plan in order to plan. A Forward search is much more of a "blind search", in the action space at least.
I don't remember where I heard it, but someone suggested an analogy of finding an ant on the tip of a leaf of a tree by starting at the trunk. The any has a better chance of finding you at the trunk than you have of finding the ant. That doesn't completely fit, but it's something to think about.
Quote:Original post by alexjc
If performance is a concern, you should be thinking about hierarchical planners anyway rather than forwards/backwards A* :-)
Alex
Yes and no. You can only get a hierarchy so far up. At some point, you still have to determine what components to use and what order to put them in. I agree with the premise, however, that using only the most granular level actions.
Quote:Original post by alexjc
If performance is a concern, you should be thinking about hierarchical planners anyway rather than forwards/backwards A* :-)
Alex
We're not talking about simple performance tradeoff here. Forward search is exponentially most costly than backtracking with that optimization, so its a matter of even being able to find a plan at all.
I think the loss of expressiveness is also far greater from hierarchical planners to regression planners than from regression planners to forward planners.
There is implementation of GOAP like algo, with source.
report - http://www.edmundlong.com/edsWiki/
source - http://www.edmundlong.com/GOAPSystemMasters.rar
Its the 2d deathmatch bot game, each team of bots has own AI from: FSM, GOAP, team FSM, team GOAP.
report - http://www.edmundlong.com/edsWiki/
source - http://www.edmundlong.com/GOAPSystemMasters.rar
Its the 2d deathmatch bot game, each team of bots has own AI from: FSM, GOAP, team FSM, team GOAP.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
