Planning Multi-unit Maneuvers using HTN and A*

HTN planners are great for problems with hierarchy as i.e. resource or unit planning. William decided to combine HTN planners with A* because this allows for finding the best plan. To do so, he starts with an initial top-level plan which he expands until the plan consists of primitive tasks. The planner generates multiple alternative plans and estimates the costs for each of it based upon the world state. The costs are then evaluated to select the best possible plan. Target of this way to handle things is to generate good solutions and not many solutions. The implemented planner must be efficient, generate useful mission briefings and create error messages when the planner fails to generate a valid plan. The planner to implement must be able to easily add new methods, and to do forward and military style reverse planning. The quality of the generated plan is important. While any plan can have bad positions, bad coverage, and make insufficient usage of resources, a good plan will contain good unit positioning and manage usage of all units in an optimal way.

When using HTN planners the top-down approach in planning reflects the problem domain of the plan to create. For each (partial) plan, costs are assigned which are calculated using the world state delta plus the risk to execute this plan plus the preferences of that plan. The multitude of plans are called plan space. Each plan space keeps track of the world states. This is necessary because if we can define world states for the start and end task of the plan, then we can estimate the plan costs.

As stated in the previous paragraph, the plan costs are based upon the delta of the world states. Since the planning breaks down the plans and sub-plans into tasks, we have to determine the costs for each task to perform (since they will, in the end, create the delta between the world state at the start and the end of the plan). The task costs are the sum of the task duration and the task risk. To weigh the resulting costs, a task preference influences (i.e. via a subtraction) the task costs. But now, how to we get the task duration? The task duration can either be the effective task duration if it's a primitive and if the inputs to that primitive are available, or the difference between the maximum time of the children execution time and the minimum time of the children execution time, if it's a task consisting of several sub-tasks. Finally, if none of the above apply, the task duration can be the lower bound estimate (given by a designer). The plans and their costs are then evaluated using A* "best first" search for planning.

William gave some examples of tasks to plan and how the costs are calculated. In his example he wanted to transport a group of soldiers from point A to B. The created plans included several solutions about where to pick them up, or even if it's worthwhile to pick them up. Each sub-task (i.e. drive to pick up location, let soldiers move to pick-up location, drive to delivery point, deploy, ...) is estimated and taken into account.

He talked about some technical issues he had encountered and how he solved them. When working with planners, you encounter binding problems. That is, you have to assign values to variables and check their consistency. STRIPS planners usually have implicit bindings. This binding becomes a problem when you have to cope with large range of values (he gave us the number 16,000 waypoints), when you write most of your planner code to constraint binding and if you have a lot of branches to handle in order to find a good plan. The work around consists of using procedural pre-conditions, abstracting and/or reduce the world state values and use explicit binding.

Using Military reverse planning helps to limit the options to evaluate. Reverse planning means that I take a look at i.e.for example an objective to attain, and I ask the question "What do I have to achieve that?" An answer could i.e. be "I have to send in 5 units." You then ask yourself what you have to do to send in 5 units. In this way, step by step, you will not only elaborate what you have to do to attain the objective, but also which resources you need (i.e. transportation, support, waypoints, landing points, etc). When planning this way, you might find it useful to take the output of one planned task as the input of the next tasks.

Compared to STRIPS planners, HTN planners allow more control and limit the branching. HTN even helps limiting the combinatorial explosion. To learn more about HTN planners see the links in the Killzone 2 related part of the report.

Interesting links:

STRIPS: A new approach to the application of theorem proving to problem solving.
Classical AI Planning: STRIPS planning
Goal-Oriented Action Planning (GOAP)
Automated planning and scheduling

Approaches to Interactive Narrative Generation and Story Telling

He started with a short lesson in history, telling us about stories in action games, stories in adventure games and finally stories in action-adventure games. For each genre he broke the history into different stages. The stories in action games for example began with a rough background story which was weakly integrated into the game play. Later action games then used the story to connect missions. In either case, the story is pre-written and offers little to no flexibility. Within the missions the story is not included.

Adventure games also made usage of pre-defined stories and allowed for limited player interaction with the environment. They have evolved to a better interface usage and more complex story graphs but still made use of a pre-written history. Only the latest adventure games, while still pre-written, have more elaborative narrative using multiple character perspectives. The action-adventures integrate action and story. The story is still pre-written and the mission structure remains.

As a conclusion to this historical approach, one can say that the story is always pre-written and has a small branch factor. The influence by the player on the story is limited and not scalable. Daniel revealed to us his utopia, where the player is part of the story, changing it through his actions. The story should be scalable and allow large, complex worlds. Domain independency would be ideal. This would allow one to create a general engine which can generate different stories independent of the game domain or genre. Through the flexibility re-playability should be achieved and enable the player to immerse more into the game. Target is not to create better stories, but to create them dynamically, faster and cheaper.

An important part of dynamic story creation is the dramatic structure which can be described using Gustav Freytag's pyramid. This pyramid analyses the plot of a story by slicing it into different parts such as the exposition, the climax and the ending. They different parts are separated by events that lead from one part to another: the exposition passes through an inciting incident to the climax, which consists of a rising action and a falling action. The climax then uses a resolution to pass to the proper ending. Different solutions can be used to create dynamic storylines: Plot graphs, Bayesian networks, planning and drama structures.

A solution presented by Daniel is called GADIN (Generation of Adaptive Dilemma-based Interactive Narrative). The idea behind the project is that specific focal points create dramatic tension and everything in between these focal points lead up to these focal points. This is done using five dilemmas (betrayal, sacrifice, greater good, take down, favor). A story consists of a sequence of dilemmas with story events leading from dilemma to dilemma. The events are controlled by the drama engine and triggered by the player's actions.

The drama engine of GADIN makes usage of a knowledge database which contains characters, story actions and dilemmas. Through a narrative generator, which is a planner, and a user model which is used to predict user actions, the story is generated and presented to the user who reacts to it. The user actions are used to trigger new story elements in the narrative generator. To select and generate the new story elements, the narrative generator makes usage of the current game state and a dilemma. It tries to generate a story using those parameters which may either fail or succeed. If a story generation fails, the generator selects another dilemma and re-iterates the story generation. Once this succeeds the plan is presented where possible and the dilemma is presented when valid (through user actions). This leads to a new state which re-iterates the story generation. GADIN has been evaluated using a kind-of turing test: One GADIN story containing only NPCs and one soap opera have been taken and presented online to 127 users in soap and game forums. 42.5 percent of the users had chosen the second story (the soap opera) as being the one generated by the computer. Now, one has to wonder if this "small" amount of replies and comparing only two stories is valid. Personally, I would prefer giving 10 choices with 5 cg and 5 soap stories and let a larger amount of users select the cg ones. And even then... the biggest problem of the current GADIN implementation is the fact that it does not produce good storylines.

Directly after Daniel's speech a panel was held. Daniel said that combining autonomous agents and storytelling was new to academia. It has been said that it could be a good idea to separate NPC into a character agent and an actor agent, taking into account the storyline generated by the story planner. But then, where do we put the line between story line control and normal AI? The story line is high level and determines general goals for the character which have to be achieved to reach the next dilemma point. The actor AI could take into account the character's beliefs and goals to trigger accurate actions that would push him towards that goal. Also, the story generator could be used to generate content for the gaming world or avoid re-spawning of enemies at places that have already been visited. As you can see, the story generation feature will have a huge influence not only to the game play but also to the content creation in future games.

Dramatic structure
Freytag's pyramid
Generation of Dilemma-based Narratives: Method and Turing Test Evaluation
Dynamic Generation of Dilemma-based Interactive Narratives (GADIN)
Facade AI

Page 5