Planning Muli-unit Manoeuvres using HTN and A*

Fastest take away slide ever!

William van der Sterren, AI Consultant at CGF-AI and Remco Straatman in the panel discussion.

William’s presentation will discuss the application of HTN and A* to help plan and coordinate groups of units. In the context of a turn-based strategy game, he’ll show how a planner can be used offline to create stimulating new scenarios for current games without the need for manual scripting.

Interesting application of planning on doing strategy in action based games. Would be great if it got fast enough for real time RTS and FPS use. I merged the panel questions onto the end of this – R is Remco Straatman.

Going to treat HTN planning like pathfinding, starting with a node and working on it step by step. The difference to pathfinding is that planning can have combinational explosions of complexity.

PlannedAssault is a mission planner for ArmedAssault which generates a combined arms assault for the user, which basically outputs unit commands and choices – the mission script. These games have a large amount of units but it is hard to have a meaningful defence or assault.

While it is an offline planner, it does have to deliver it to the player in a few minutes. Has to explain what the human has to do as well, as well as when things fail to plan from human-placed units, tell the human!

Military options also often plan backwards from the result they want so the planner can deal with this, as well as normal forward planning.

Basic military action is form up, then formation attack. When planning military actions, there are valid working plans which are terrible ideas, such as sending tanks into woods and infantry in the open.

Hierarchical Task Network Planning is about taking a task and decomposing it into different parts. When a task is chosen its actions are refined into a set of partially ordered tasks – example is TransportedMove with a passenger.

Can bias the players choice of vehicle or action – so if a truck driver, prioritise the use of trucks even if they could walk the distance in a similar time.

Cost estimates are done on assumptions – no obstacles, max speed, and preference for truck usage to move around.

A normal implicit planner will check lots more plans and combinations then is usually feasible (such as 16,000 waypoint nodes). Making it explicit means you can specify depth, amount of plans to return and so forth – which helps when you have 3 transports with 3 passengers, with hundreds of combinations normal.

Doing backwards planning from military manuals – such as an air assault, goes “how do you want troops to end up” which gives “how you attack” then “what units are in what air vehicle” and so on back and back.

This helps cut down the possibilities, and is natural for the military.

Panel Discussion

Why did you choose HTN not STRIPs or anything?
R: Had a look at FEAR’s work and had an implimented version of it, but when there was the possibility of actions being needed to use in order, and designers wanting more control or adding new enemy types, it was a case at looking at other ones. HTN was used since you can handle procedural preconditions, and can do designer made actions.

Any difficulties doing HTN on PS3?
R: Yes, mainly speed and when it had combinational explosions. There was optimisations mainly in the interpreter, so the main plan classes didn’t need as much work. Looking to get overall speed improvements however next time.

How do you make the AI not look completely dumb if planning fails?
R: Very feasible to make the last branch a fallback behaviour as one way to deal with it. Having tools to show why certain parts of the plan failed also helps – the level designers need training to get used to stopping the simulation when something doesn’t go right.

Leave a Reply

Your email address will not be published. Required fields are marked *

Website and journal of Andrew Armstrong