STRIPS and concurrent actions
Author
I'm planning to write a STRIPS implementation (based off the explanation given from the FEAR GDC presentation) within the next four months, and I'm trying to figure out how to gracefully handle an entity performing several actions at the same time (ie, moving and shooting, moving and searching, etc.) Many games give the player several components of their avatar that can be controlled at once, with the upper end example of this shown in a strategy game with multiple units to control. Having an implementation that allows an arbitrary number of different ways to interact with the world (for example, allowing problem solving with a tank that has three independent turrets, making it possible to have four concurrent actions)
I've heard of Hierarchical Task Networks, but I can't find an explanation that explains them for me all that well. Is that what I'm looking for to solve this kind of problem elegantly?
No. The common pattern for an FPS is behaviors. An example set of behaviors for an NPC would be:
Move to position
Move while firing to position
Take cover
Peak & Lean
throw grenade
Dodge grenade
Search
Idle Patrol
Each behavior is finite in length: move to behaviors end when the move is done. However, any behavior can be interrupted at the discretion of the behavior chooser.
Each behavior has a heuristic that either returns a yes/no answer for "can you run now" or returns a score indicating how good a choice the behavior is currently. The behavior chooser evaluates the scores of its behaviors each timeslice. You bias the choice towards the currently running behavior.
This system was/is used in Halo & FEAR makes some use of this as well (IIRC). It's also been used in a bunch of other titles because it has some great advantages: adding new behaviors is modular & thus trivial. Tuning behaviors is simple: modifying the heuristic, tuning a number that weights the behavior. You can create different NPCs by just modifying their behavior load-out.
It's the inputs to this behavior system that really make the difference between old and new gen: better perception systems, better analysis of the environment, better analysis of strategy/affordences, etc.
-me
Move to position
Move while firing to position
Take cover
Peak & Lean
throw grenade
Dodge grenade
Search
Idle Patrol
Each behavior is finite in length: move to behaviors end when the move is done. However, any behavior can be interrupted at the discretion of the behavior chooser.
Each behavior has a heuristic that either returns a yes/no answer for "can you run now" or returns a score indicating how good a choice the behavior is currently. The behavior chooser evaluates the scores of its behaviors each timeslice. You bias the choice towards the currently running behavior.
This system was/is used in Halo & FEAR makes some use of this as well (IIRC). It's also been used in a bunch of other titles because it has some great advantages: adding new behaviors is modular & thus trivial. Tuning behaviors is simple: modifying the heuristic, tuning a number that weights the behavior. You can create different NPCs by just modifying their behavior load-out.
It's the inputs to this behavior system that really make the difference between old and new gen: better perception systems, better analysis of the environment, better analysis of strategy/affordences, etc.
-me
Hey, I did just that last year :) Implemented my own FEAR-like planner. Worked pretty well too, and I had tons of fun. To answer your question:
One way, is, like Palidine said, to combine actions into ones in your action space description.
For your tank example, you might want to consider each turret as its own agent, who all recieve their goal-state from the main, "tank" agent.
Another way is through constraint-posting planners, or even scheduling algorithms. They allow you to plan for concurrent actions. But its way beyond STRIPS-like planners, both in terms of implementation complexity and ressource-hungriness.
One way, is, like Palidine said, to combine actions into ones in your action space description.
For your tank example, you might want to consider each turret as its own agent, who all recieve their goal-state from the main, "tank" agent.
Another way is through constraint-posting planners, or even scheduling algorithms. They allow you to plan for concurrent actions. But its way beyond STRIPS-like planners, both in terms of implementation complexity and ressource-hungriness.
Author
Ah, I'm sorry I must have phrased my question wrong. What I meant wasn't simply allowing for modular actions. I've already got that bit... in fact, I'm already using that in my current game project to great effect (though it isn't a planning system). What I want to do is extend a planning system like STRIPS to allow for multiple actions to be taken at once in a plan. For example, lets take an FPS: with what you're talking about, you have a move action and a shoot action, as well move while shooting action. I want to figure out how to cut that last action out and allow a STRIPS planner or something like that to know how to move and shoot at the same time without being explicitly told how.
An FPS player is very much like a tank. Their movement systems (chassis) are independant from their targeting and shooting systems (turret). Each of these has its own set of actions. The movement systems might have actions like "jump", "moveTo", "idle", or "duck", while the aiming systems might have "aim", "aim and burst fire", "aim and spray", "press button", and "idle". Rather than artificially combining skills to create things like "shoot and duck" or "jump and spray", I want the AI to be able to figure out the basics on its own, and combine these basic skills on its own.
More importantly, I want to make a very general solution that can apply to more than just, say, an FPS. If I wanted to extend it to, say, a flight sim, where the entire squadron of fighters or bombers is hooked up to the same planner to coordinate their movements, it should be able to handle it.
I guess a better question is this: can I extend a STRIPS or STRIPS-like planner in order to allow for multiple agents (is that the correct term) to act simultaneously within a single plan? If not, is there a system that can handle this kind of thing?
[edit] Sorry, Steadtler, I didn't see your post! I'm going to do some searches on constraint-posting planners and scheduling algorithms, thanks!
An FPS player is very much like a tank. Their movement systems (chassis) are independant from their targeting and shooting systems (turret). Each of these has its own set of actions. The movement systems might have actions like "jump", "moveTo", "idle", or "duck", while the aiming systems might have "aim", "aim and burst fire", "aim and spray", "press button", and "idle". Rather than artificially combining skills to create things like "shoot and duck" or "jump and spray", I want the AI to be able to figure out the basics on its own, and combine these basic skills on its own.
More importantly, I want to make a very general solution that can apply to more than just, say, an FPS. If I wanted to extend it to, say, a flight sim, where the entire squadron of fighters or bombers is hooked up to the same planner to coordinate their movements, it should be able to handle it.
I guess a better question is this: can I extend a STRIPS or STRIPS-like planner in order to allow for multiple agents (is that the correct term) to act simultaneously within a single plan? If not, is there a system that can handle this kind of thing?
[edit] Sorry, Steadtler, I didn't see your post! I'm going to do some searches on constraint-posting planners and scheduling algorithms, thanks!
Let me know if you find anything related to gaming. Everything I found was *very* academic. Which is ok for me, but I would like to see some hands-on stuff.
Im still torn between polishing my STRIPS-like planner or working on a constraint-posting one.
Im still torn between polishing my STRIPS-like planner or working on a constraint-posting one.
Author
MSN coughed this up, actually:
http://www.ict.usc.edu/publications/ICT-TR-01-2002.pdf
I haven't finished reading it myself, but many of the ideas contained in there seem to apply to games, even if the document is fairly academic. A lot of the things mentioned might not be the way I'd personally like to do it, but it does give me ideas.
What is described seems (from what I've read) to be a fairly straight forward extension of a STRIPS planner, with an emphasis on dealing with the fact that tasks don't take place instantly or simultaneously.
Its not quite what I was looking for when I asked the question, but it seems like planning for multiple agents at once would be a lot more work than I'm willing to put into this project, so I think I'll be dropping that requirement. After all, most of the effects can be done with compound actions...
What I'm ultimately hoping to achieve is a a really modular way to create NPCs in an open world... something that scales with the options you give it and does interesting things without having to be scripted. Obviously, thats nothing new, but it will still be really interesting to work with, and if I code it right I should be able to plug it into other projects with minimal effort.
What I need to figure out now is how to work efficiently with uncertain or non boolean components. Does anyone have any advice in that regard?
http://www.ict.usc.edu/publications/ICT-TR-01-2002.pdf
I haven't finished reading it myself, but many of the ideas contained in there seem to apply to games, even if the document is fairly academic. A lot of the things mentioned might not be the way I'd personally like to do it, but it does give me ideas.
What is described seems (from what I've read) to be a fairly straight forward extension of a STRIPS planner, with an emphasis on dealing with the fact that tasks don't take place instantly or simultaneously.
Its not quite what I was looking for when I asked the question, but it seems like planning for multiple agents at once would be a lot more work than I'm willing to put into this project, so I think I'll be dropping that requirement. After all, most of the effects can be done with compound actions...
What I'm ultimately hoping to achieve is a a really modular way to create NPCs in an open world... something that scales with the options you give it and does interesting things without having to be scripted. Obviously, thats nothing new, but it will still be really interesting to work with, and if I code it right I should be able to plug it into other projects with minimal effort.
What I need to figure out now is how to work efficiently with uncertain or non boolean components. Does anyone have any advice in that regard?
Here's how I used A* to plan for multiple agents (using A* for a task scheduler for work, actually). My state space is encoded into a std::bitset (so I could an use arbitrary number of agents). Each agent has 2 numbers associated with it...a "Task ID", and "number of time ticks left until this agent is finished with this task". This was complicated a bit by keeping track of inventory, etc, but ignoring that, there are basically 2 types of "actions" available to the planner:
1) assign a task to a given (available) agent
2) wait for a single "tick"
Obviously #1 is actually a collection of all possible valid permutations of tasks which can be assigned to agents. As for #2, the wait action had the effect of decreasing all the agents "busy till..." counters, and if any of the counters went to 0 that signified they'd finished, whereupon the task they were assigned was marked as done, inventory updated, etc. and the agent was ready to be assigned another task.
The state search space is HUGE, so 2 warnings: you need a _really_ good heuristic, and you need a really fast A* solver. None of the free C++ libraries I found were remotely fast enough. I ended up writing my own with 2 sub-components: a very fast hash-map (as fast as Google's dense-hash, in this application anyway....was using Google's but mine is a very simple version with 0 frills, but easier to move around {1 file}) and an automatically partitioning Heap-On-Top queue.
1) assign a task to a given (available) agent
2) wait for a single "tick"
Obviously #1 is actually a collection of all possible valid permutations of tasks which can be assigned to agents. As for #2, the wait action had the effect of decreasing all the agents "busy till..." counters, and if any of the counters went to 0 that signified they'd finished, whereupon the task they were assigned was marked as done, inventory updated, etc. and the agent was ready to be assigned another task.
The state search space is HUGE, so 2 warnings: you need a _really_ good heuristic, and you need a really fast A* solver. None of the free C++ libraries I found were remotely fast enough. I ended up writing my own with 2 sub-components: a very fast hash-map (as fast as Google's dense-hash, in this application anyway....was using Google's but mine is a very simple version with 0 frills, but easier to move around {1 file}) and an automatically partitioning Heap-On-Top queue.
Quote:Original post by lonesock
Here's how I used A* to plan for multiple agents (using A* for a task scheduler for work, actually). My state space is encoded into a std::bitset (so I could an use arbitrary number of agents). Each agent has 2 numbers associated with it...a "Task ID", and "number of time ticks left until this agent is finished with this task". This was complicated a bit by keeping track of inventory, etc, but ignoring that, there are basically 2 types of "actions" available to the planner:
1) assign a task to a given (available) agent
2) wait for a single "tick"
Obviously #1 is actually a collection of all possible valid permutations of tasks which can be assigned to agents. As for #2, the wait action had the effect of decreasing all the agents "busy till..." counters, and if any of the counters went to 0 that signified they'd finished, whereupon the task they were assigned was marked as done, inventory updated, etc. and the agent was ready to be assigned another task.
The state search space is HUGE, so 2 warnings: you need a _really_ good heuristic, and you need a really fast A* solver. None of the free C++ libraries I found were remotely fast enough. I ended up writing my own with 2 sub-components: a very fast hash-map (as fast as Google's dense-hash, in this application anyway....was using Google's but mine is a very simple version with 0 frills, but easier to move around {1 file}) and an automatically partitioning Heap-On-Top queue.
The method is admirably simple, but I wonder if discreetizing time will ever work for games, since we want agent to have a fairly low reaction time (I wouldnt go for anything more than 250ms). Could work if you only make plans that are *very* short in terms of execution time... but else, yeah the space will be too big to be able to plan in a reasonable span of time.
Quote:Original post by Steadtler
The method is admirably simple, but I wonder if discreetizing time will ever work for games, since we want agent to have a fairly low reaction time (I wouldnt go for anything more than 250ms). Could work if you only make plans that are *very* short in terms of execution time... but else, yeah the space will be too big to be able to plan in a reasonable span of time.
If I were to put this into a game, I'd probably use this in a hierarchical fashion..."squad level planning" if you will. The highest level would order squads around, the next level would order individual members of the squad, the lowest level would plan actions for a single soldier. Each level above the lowest would need to discretize time, but each level would have it's own tick time. "Move Squads to Sector C, but continue to Guard Sector A" might take 1 minute...so a tick of 10 seconds would be plenty of resolution (note the implied use of a much coarser pathfinding-graph). "Squad A, flank player's position" might take 5 seconds, so a resolution of 0.5 seconds would be plenty. And for the individual level, there is no multi-agent component, so no tick is required.
It's certainly possible to use STRIPS for multiagent planning. The simplest way is to replace the action space with the cross-product of the action spaces of the individual agents.
For example, if a single agent has two actions (move, shoot), then two agents "acting as one" will have four actions ((move,move), (move,shoot), (shoot,move), (shoot,shoot)).
Ok, granted, there are some additional complications, such as eliminating illegal actions (e.g. both agents can't move to the same block), but theoretically this kind of system would be capable of doing co-operative planning (e.g. agent one gets the red key while agent two gets the blue key, thereby halving the time to get both keys).
- Mikko
For example, if a single agent has two actions (move, shoot), then two agents "acting as one" will have four actions ((move,move), (move,shoot), (shoot,move), (shoot,shoot)).
Ok, granted, there are some additional complications, such as eliminating illegal actions (e.g. both agents can't move to the same block), but theoretically this kind of system would be capable of doing co-operative planning (e.g. agent one gets the red key while agent two gets the blue key, thereby halving the time to get both keys).
- Mikko
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
