On the simplest level an agent does two things peforms actions and determines which actions to perform. So after reading an article on Will Wrights "Spore" project I thought about my own work and began to wonder if instead of having a set of predefined actions that an agent can perform. If it would not instead be possible to to allow for generated actions, In which the agents create the actions they can perform and can then share these actions with each other agent. Question is how to achive this? My first thought is to have set of generic atomic actions that can be combined to form more complex actions. Then relate those actions to properties that objects possess. The ideal of course being not to have extenable properties that can be added on to a list of basic properties. Consider a branch. It has a set of characteristics that describe it as a branch. It then has a set of properties that an agent can apply to it based on the agents own characteristic and the actions it can perform. For instance do you eat a branch? That depends on if the agent knows how to eat and whether it eats woods. But then the question of defining atomic actions comes into play. Is eating an atomic action or complex one? If eating is an atomic action then is eat branch a complex action? If eat is a complex action then what atomic actions would it be made from? The idea of atomic actions is that they can becombined to form complex ones as such they should be combineable with other atomic actions and objects with related properties.

What you are describing here is a plan, which is comprised of a sequence of atomic actions.

Planning is a big AI topic and a good start is to search for "STRIPS planning". I don't know how good the quality of the online articles you'll find are but I can recommend the book "Artificial Intelligence a Modern Approach", which goes into STRIPs in a reasonable amount of depth.

For a good quick overview of how planning can be applied to games see "Applying Goal-Oriented Action Planning to Games" by Jeff Orkin in AIGPW2. Jeff has been implementing a STRIPS like planning system into Monolith's game FEAR, which should be in the stores sometime soon. That right BrianL?

I'm familer with STRIPS and planning. But what I'm interested in is a system of buildings actions from components. While this is as an aspect of planning. I am instead considering complex actions to be a kind of reuseable sub plan.

So a plan might be: move to ladder, climb ladder, aim gun at car, fire gun.
Where move is an atomic action, and climb, aim, and fire would most likly be complex actions.

I'm not sure what you are asking for. If what you define as "complex actions" are sequences of other actions then what you have there -- as defined in the AI literature -- is a plan. It may be a simple plan, but it's a plan all the same and there are several planning methodologies that utilize the use/reuse of such "sub-plans"

The effect of each atomic action, sub-plan or plan is a change in state and I would therefore suggest that the question of whether one is called “complex” or not, as far as achieving a goal state is concerned, is moot.

i would guess it is to what degree you wish to decompose down into for atomic actions. perhaps in the case of the eating wood, it could break down like this:

Atomic Actions:
OpenMouth, CloseMouth, Swallow, Taste(FOOD_TYPE)

Complex Action (L1):
Chew(CONDITION) = DO OpenMouth, CloseMouth UNTIL CONDITION

Complex Action (L2):
Eat(FOOD_TYPE) = OpenMouth, CloseMouth IF Taste(FOOD_TYPE) THEN Chew(Swallowable), Swallow

Complex Action (L3):
EatBranch = Eat(Branch)

just a thought, do i at least have the right idea?

screwtape, yes,yes, that is the sort of thing I had in mind. Form looking at your response I'm wondering if perhaps the atomic actions could not simply be:
Use (Object)
Move (Obect) to (Location)
Sense (Object) with (Object)
Compare (Object, Characteristic) to (Object, Characteristic)

From there it might be possible to build up any complex action.

So:

EAT(FOOD_TYPE) = Get(FOOD_TYPE), Move(FOOD_TYPE) to (MOUTH), if(Taste(FOOD_TYPE) then USE(MOUTH).

hmm, I wonder if some sort of knowldege action would also be required, so that in the Taste action it would check whether the FOOD_TYPE was in in effect edible.

fup:

The idea is that, in this case when the agent has to determine what do with a branch, it can choose from a set of actions to perform on the branch based on its properties or attempt to learn an new action to perform on the branch either from existing actions it knows or by creating a new one.

Take eat for example, since its a known complex action the agent doesn't have to repeat the the planning proccessing associated with eating it simple executes the eat action. Or in another case the agent reaches a river if it knows how to perform the action build bridge then the planning required to determine how to pass the river might consist of choosing between searching for a place to cross the river or building a bridge.

There is still the issue of how to build complex actions, which in it self is in essence a planning problem.

What you're really describing here is heirarchical planning, where at an abstract level you describe the action as 'Eat', which becomes the descriptive title of a sequence of atomic actions further down the heirarchy (OpenMouth, InsertFood, CloseMouth, Chew, etc).

If you want to follow this path (sorry about the pun), then you should look at describing the sorts of things agents want to do in terms of abstract actions and then planning becomes finding a set of atomic actions that will achieve this. So, for example, you might have an abstract action of 'CrossRiver', which involves two strategies: (1) BuildBridge; and, (2) Swim. (these could be thought of as PassOver and PassThrough). For each strategy, there would then be a number of different plans that might be viable solutions. E.g., building a raft and paddling across would be akin to a floating bridge; or building a stone bridge as compared to a felling a tree across the gap. For swimming, there might be different stroke techniques that could be applied repetitiously to traverse the river. Get my point?


Having said all of that, I think a more interesting problem (because heirarchical planning is a fairly well understood problem) would be, 'how do agents couple actions in parallel to produce new, more complex, actions?' For example, I can hold a bucket of water and swing my arm in a vertical motion to produce a nice party trick (not spilling any water). If I was given the task of carrying a bucket of water without spilling any, I could use this technique to achieve that (combined with walking) and it would be more stable than say balancing it on my head as I walked. None of the actions taken in any sequence would achieve the same result. At a minimum I would have to combine in parallel holding the bucket, swinging my arm and walking. Get the picture? The interesting planning problem is how does one efficiently consider combinations of atomic actions in parallel. Are there certain combinations of atomics that work well together (and I believe the answer is yes; e.g., holding and walking are a great way to move items around... but only if they don't weigh much)!

Whatever you choose to do, keep us posted with your projects progress please. I'd be interested to hear what you find out works well!

Cheers,

Timkin

fup, that is correct. I am using the same planning system (slightly extended and optimized, with a different action set) for 'Condemned: Criminal Origins', a Xbox 360 title.

Jeff did a AAAI presentation on our tech last year. Try searching for "Symbolic Representation of Game World State" on google. Our actions are higher level than the OP talked about, but we have somewhere between 100 and 200 atomic actions the AI can do, based on around 20 to 50 goals. As this is the case, planning efficiently became critical, so high level actions made sense.

If you are interested in a heirarchical system, you may want to look at HTN planning (Heirarchical Task Network). I haven't worked with these yet, but the ideas look very interesting.

If you go with straight state space planning, be aware that there are all sorts of 'interesting' problems to deal with in the context of a game; many times you want a particular ordering to your actions when multiple options are availible. For instance, lets say you had an NPC holding a weapon who wanted to pick something up. Should they walk over it it, and then holster their weapon, or should they holster their weapon first? There are certainly ways around this working with raw state space planning, but it can get messy. Look up the 'Sussman Anomaly' for a good reference.

Plan space (including partial order planning) present some interesting solutions I haven't had a chance to explore yet. Executing actions in parallel is also an interesting option, though depending on the engine/art assets you have, this may be messy (what can be done in parallel may be constrained).

In any case, this is a huge field with a massive amount of literature supporting it. Planning without predefined operators (actions/behaviors) is part of this field, but I would suggest dipping your toes in first before jumping in to more advanced parts. :)

Timkin thank you very much for the post, its given me a whole new perspective to think about. I was originally think of atomic actions begin performed sequentially I had not even considered having them performed in parallel. It is definitely an intrigue idea and could produce some interesting results. I was thinking about the organizational structure of actions and was originally thinking them in terms of chains, but I’m now considering a tree structure instead. Where sibling nodes represent alternative actions plans to accomplish a higher level parent action. But I’m still wondering how to go about modeling parallel actions, let alone plan them. I’ll have to think the problem some more and see what I come up with. Hopefully this project will turn out better then my frame driven world idea, which proved difficult to work with, as anyone who’s done any programming with dynamic objects can understand.

BrainL I read the article you mentioned it was interesting article and I’m looking forward to see games that use a system like it describes.

Quote: Original post by TechnoGoth
But I’m still wondering how to go about modeling parallel actions, let alone plan them.

You'd model them in whatever means you want to model sequential actions... so, for example, if you were using STRIPS, you'd have, for each action, a list of pre-conditions and post-conditions. The problem of planning with parallel actions adds in a 'resource allocation' dimension to the planning problem. Your agents have a finite number of actuators and some or all of these will be required to execute each of the actions that agent can perform. The ability to perform actions in parallel involves the assignment of independent subsets of actuators to each action. For additional complexity though, you can allow actions to 'piggy back' resources. For example, you want to carry your cup of coffee to your desk. This would involve picking up the coffee, balancing your arm and walking forward while maintaining a firm grip on the cup. Let's say that half way there you decide to grab a donut and carry that to your desk as well. You have a free hand (unused actuator/resource) which you can apply to the task of picking up and holdin the donut. Now, the carry-the-donut-to-the-desk action piggy-backs on the movement action already instigated for the carry-the-coffee-to-the-desk action. Get the idea?

No, it's NOT trivial to implement! However, techniques like constraint-based planning can be used to make feasible systems in small domains. You might also want to consider Mixed Integer Linear Programming (MILP). I've recently been introduced to as a method of solving finite horizon planning problems... it looks promising for many domains!

Cheers,

Timkin