Quote: Original post by Wombah
I was thinking about a backwards planner, such that instead of adding actions (which are in general just state transitions) to the agents current state, you try to 'backengineer' the goal state. If the agent wants to open a door X that is locked, you search for an action that results in that state ('door X open'), and finds the 'open door X' action. Now this action in turn has a start state saying 'door X is unlocked', meaning we now have to find an action that results in the door being unlocked. Looking through our available actions we find 'unlock door X', which in turn has a start state 'has key for door X' etc...

Thats how many planners works, actually. Check out the link I posted earlier about partial-order planning.

Quote: Original post by Wombah
@ Timkin
I would be most interested in reading your PhD... thesis?... if it's available.

Unfortunately, for IP reasons, it's not available for general consumption until later next year. I do have a paper I published at IAV'04 that gives an over-view of the replanning paradigm. If you'd like a copy, send me an email (the address is in my profile).

Cheers,

Timkin

If you have any questions about Jeff Orkins planner, feel free to ask me. I am on Monolith's other team - I was the AI programmer on Condemned which used the same code base. While I didn't write the planner, I worked with it for 2 years.

The heuristic was fairly simple. As with most base AStar implementations, it was based aroud the cost to the current node in the graph and plus an estimation about the cost to the goal.

Each action/operator applied introduced another edge in the graph. Each action had a fixed cost. In the future, it probably makes sense to make this value a bit more dynamic as the logical cost of walking two feed and running across a football field vary. We didn't represent this degree of information in the planner.

The estimate was simply the number of unsolved properties in the state.

After working with the system, I think what best decisions Jeff made initially were:

1) What gets represented in the planner. If you go too low level, combinational complexity will kill you. If you go too high, you can't reason enough information.
2) Setting constraints on the system. The 'state' objects had a fixed set of properties, which allowed us to keep copying the state cheap. Initial attempts with a more dynamic state were problematic.
3) Degree of variable support. We supported variables in the planner, but in limited ways. At no point did the planner expand variables to their permutations.

Basically, we almost always favored low complexity and simplicity over expressiveness. After hitting the sussman anomaly, I looked into partial order plans, but was concerned about the cost. In a lot of ways, a hybrid state/HTN planner looks like the right complexity for our needs.

Hmm. Perhaps I should write a planner article for gamedev some time. :)

Well, I have lots of questions, but they're still on the level 'How does one make a planner?'. :)
I need to read up a bit before I get into any details. I'm trying to make an overall design for a planning system using various sources like Orkin, Nereyek, c4 from MIT and even the emotion engine. Fairly ambitious, I know, but the plan for now is to use several subsystem such as emotion etc. but keep each subsystem very low on detail. We'll see how it goes.
When (if) I get the overall design together maybe I'll post it here to get some feedback. And when (again, if) I get started on a prototype I'll be back with more specific questions I reccon.

One thing I didn't get with Orkin's planner; It uses A* to search the action graph, but how do you create that graph? Do you use partial states, since most actions only have preconditions on a subset of the world? Do you just add in all actions with their preconditions and results as nodes and then add edges wherever possible in some form of precalculation step? It seems to me that there are relatively few actions that can be connected directly...

Also, were there any form of uncertainty in the FEAR planner? I haven't read all of Orkin's cited papers, just the three fup linked to so maybe this is answered there. I'll read the others as soon as I get around to it.

The basic idea is that you generate neighbors by finding actions which can solve something in the current state. The simplest implementation would test every action when looking for neighbors. Usually, you can do better by precomputing actions which can potentially solve different properties.

I believe we put out an SDK containing all of the planning code. Its a pretty massive download, but you might want to check out the 1.04 release. Look at the module named 'aiplanner.cpp'.

If you are serious about planning, you might want to look at the book 'Automated Planning: Theory and Practice'. It covers the field fairly well.

We didn't support uncertainty in the planner, though other parts of the AI system did small amounts of uncertainty modelling. The planner itself is fairly basic - any complex condition handling is provided by separate, optional validation functions.

What most of you seem to be talking about is actually a problem solver, not a planner. Usually, if you're using A*, you're making a problem solver, searching the space of states for a solution. A planner searches the state of partial plans for a plan from start state to goal state.

A good reference you may want to look at is STRIPS, the Stanford Research Institute Problem Solver (formed before the term 'Planner' emerged). Wombah, you provided a rather good explanation of how it works, so I shan't repeat that here. It's a regression partial order planner, and is rather elegant, though has some limitations (granularity of plans, complexity of preconditions etc.).

I find it's much easier to think of planners and problem solvers in mathematical terms (despite my continuous moanings of how long-winded mathy explanations are!), perhaps you should take a look at the field of discrete mathematics? Once you understand planners from that perspective, it's just a case of translating that to code. It'll help you make general-purpose planners too.

If you want any help on planners, AI and the like, feel free to email or PM me, I just finished a course in all this stuff (the exam was yesterday, in fact!), and am interested to learn more. Good luck, anyway, whatever you decide to do :)

Ive looked at using a planner mechanism for the basic behavior control of npcs in a simulation.

NPCs have persistant goals (eating sleeping business self-protection, etc...)
NPCs have sets of solutions to achieve the goals (skills)
More than one solution may be avaiable to the NPC and there must be a way to choose the current 'best' (matching preferences as well as the current situation).
Solutions usually have sub goals each requiring its own solution -- the system is hierarchical(recursive).

Significant problems for a realic simulation:

Priority mechanism to decide which goals are best pursued at the current time.
Priorities can adjust evaluation functions used to judge cost/risk of different solutions. (if you are very hungry you may be more willing to attempt more dangerous/distasteful actions to get food....)

Evaluation of the metrics required to decide of which solution to pursue ( and since the situation may continue to change, constant reevaluation of likely solutions). Opportunistic behavior to be reactive.

The metrics are often probabilities and projections because many future situations are not yet known. Different objects may have different tolerances/thresholds for risk. Cost vs risk analysis... (costs may be a vector of different factors with each vector having different 'value' to different objects).

Current tasks (solutions being executed) may have momentum that boosts their priority to prevent oscillations between tasks of similar priority. Partial success of goals can be acceptable.

Some goals are maintenence of 'tools' that maximize flexibility (keeping many solution options open). Some solutions may be selected as 'best which keep sufficiently probable subsequent steps (or even for other goals -- metric may count general utility of a goals achievement).



Notice that in all this, the planner is actually only a small part of the total AI system.

Quote: Original post by BrianL
The basic idea is that you generate neighbors by finding actions which can solve something in the current state. The simplest implementation would test every action when looking for neighbors. Usually, you can do better by precomputing actions which can potentially solve different properties.

I see. It just occurred to me that you probably don't have to create the graph per se. You could just store actions in a map, where they are indexed by which properties of the state they affect, and then for each step look up the properties that are missing to form the goal state? That way, you avoid the 'problem' of creating the graph, but you still wouldn't have to fall back to the base case of checking all actions each step...

Quote: Original post by BrianL
I believe we put out an SDK containing all of the planning code. Its a pretty massive download, but you might want to check out the 1.04 release. Look at the module named 'aiplanner.cpp'.

If you are serious about planning, you might want to look at the book 'Automated Planning: Theory and Practice'. It covers the field fairly well.

I'm certainly serious enough about it to check out your SDK and that book. Thanks for the tips.

Quote: Original post by hymerman
What most of you seem to be talking about is actually a problem solver, not a planner. Usually, if you're using A*, you're making a problem solver, searching the space of states for a solution. A planner searches the state of partial plans for a plan from start state to goal state.

Could you explain the difference to me? The only references I could find seemed to say a planner is a particular form of problem solver.

I've read a lot of references to STRIPS, but always in the context of how the proposed planner in the article is better in some way or another, so I came too see STRIPS as the outdated base case that was either hopelessly inefficient or too static for problems such as agents in a dynamic world. It is some thirty-odd years old now after all. Might want to revise that opinion and take a look. Also, I just learned about Markov Decision Chains which also seems like something I should look into. Wikipedia is your friend.

I'm beginning to get a grasp of where I'm aiming with this. Thanks for all your input.

One (of many) problem I can foresee is how to enforce something like c4's sensory honesty. From the little I've found about that actual system, they seem to actually record sounds and images and then perform speech reconition etc. Way overkill for my needs in any case. Right now I'm thinking that the agent 'sees' statevariables just like the ones used to depict states internally. These are then stored in 'working memory', and each update they degrade if they are not still visible to the agent. Thus, something seen a while ago will have a lower 'probability' or 'certainty'. But that begs the question of what certainty to assign to things that have never been sensed?

Probably way too early to get into those specifics though. I'll assume that way works for now. To be continued...

@AP
That system sounds a lot like where I'm aiming. Is that something you've implemented, or is it a design you've made?

hymerman, I think we may have our terminology crossed. There are many types of planners (this is from memory, so I apologize if I get some of this wrong):

You can plan in:
* State space
* Plan space

Plans can be:
* Totally ordered
* Partially ordered

State space representations include:
* Set theoretic
* State-variable
* Classical

There are also many specialized types of planners such as:
* HTN
* Markov based planning
* Temporal planners

I think you are refering to state space planners as 'problem solvers'. I thought STRIPS was a state space, totally ordered planner. Was it extended to partial order?

Anon,
That system sounds very similar to our implementation. The goal/planner relationship works well.

Wombah,

Quote: you probably don't have to create the graph per se

Exacting, if you have 100 actions/operators, you only need to worry about the 5 that solve something in the current state. Its a very nice optimization. Once you know which properties each action effects, you can also filter based on the value it generates. My phrasing here depends the representation, but minimizing the number of successors at each step is important for good performance.

STRIPS may be inefficient for large plans, but as we are making games, we get to pick the abstraction. I think the Fear planner had something like 15 state properties. 150 actions/operators. At this scale, a state space planner worked fine.

I wouldn't worry much about enforcing sensory honesty. It is definitely a good goal, but its a nice surface level problem. If someone breaks it, its generally easy to fix.

For us, the sensors took whatever information was visible to them and translated it into information for goals to use. The goals/actions talked with the planner. I wouldn't try to force information into your planner representation too early, as this will just complicate your representation needs and complexity.