11-10-2010 Meeting Minutes

Agenda:
• What we’ve done?
• How we’ve do it?
• What you can do?
• What’s next?

What we’ve done

Developed an agent that’s capable of:
1. Learn from human demonstration.
2. Put a plan online and adapt it online.
3. Assets the current situation and react based on it.
4. Learning from its failure.
5. Encapsulate its learnt knowledge in a portable casebase.

How we’ve done it

1. Reading about general game AI:
a. AI Game Engine Programming.
b. Artificial intelligence for games.
c. Programming game AI by example.

2. Reading about latest research in RTS AI:
a. All papers reside in project repository in “Adaptation and Opponent Modeling” folder.

3. Reading about machine planning:
a. Machine planning papers resides in project repository under folder “CBR/CBP”.

4. Reading about machine learning:
a. Reinforcement Learning: An Introduction.

5. Understanding Stratagus code:
a. Open the code and enjoy.

Minimal requirement is:
1. Reading Santi’s papers.
2. Reading about machine learning.
3. Understanding Stratagus code.

What you can

1. Enhance current engine (60% Theory, 40% Code):
a. Human demonstration feature:
i. Adding parallel plan extraction.
ii. Adjusting attack learning method.
b. Planning feature:
i. Adding parallel plan execution.
c. Situation Assessment:
i. Converting it from static rules into generated decision trees.
d. Learning:
i. Needs intensive testing and tuning for parameters.
2. Modularize the engine (20% Theory, 80% Code):
a. Make the middle layer generic for any RTS games.
b. Let the configuration of middle layer scripted (or whatever but should be something external).
c. Modularize used algorithms. So we can use it any context suitable.
d. Develop the engine in API form.
3. Knowledge Visualize (N/A):
a. Develop tool to visualize agent’s knowledge, summarizes how it will react while playing in the game. This tool will let us investigate agent’s knowledge deeply.
4. Tactics Planning and Learning:
5. Propose other approaches for planning and learning.
6. Parallelized AI:
a. Some processing in the engine is done sequentially were it may be done in parallel. Using a distributed/parallel API (i.e. OpenCL) to parallelize the agent’s processing.

What’s next?
Tasks are divided as follows:
1. Muhamad Hesham will read about General Game AI.
2. Magdy Medhat will read about latest research in RTS Games AI.
3. Mohamed Abdelmonem will read about machine planning.
4. Islam Farid will read about machine learning (especially Reinforcement Learning).

Also we’ve agreed about the follows:
1. We’ll first enhance the engine (i.e. develop feature #1) while we are reading and building our knowledge.
2. Then, we’ll start developing the learning and planning in tactics level.

How we’ll enhance the engine developmed?
Every member of the team will be involved in the development of specific feature with either Abdelrahman or Omar. This will be done besides his readings. For now Magdy Medhat will in the first feature.

Final note, we’ll post tasks on the blog and you can track the results there.

What’s done, what’s next?

Good evening,
In this post we will give you a brief about our past research and future plans.

During the last year, We were concerned with the field of planning, learning and knowledge sharing in RTS (Real-Time Strategy) Games.

A- We started our work during our graduation project (Find it in this post) which was entitled “Adaptive Intelligent Agent for RTS Games ” (2010). We applied a novice planning technique (Online Case Based Planning) and a machine learning approach (Reinforcement Learning) in order to achieve an artificial intelligence that approaches the human behavior. We’ve made our best during this project from both research and development aspects. Below are research related aspects we’ve done:

1- Doing research using a number of papers, thesis & books as follows:

Papers encouraging research in this area:

RTS Games and Real–Time AI Research – 2003
Call for AI Research in RTS Games – 2004

Papers adopting Case Based Planning:

Case-Based Planning and Execution for RTS Games – 2007
On-Line Case-Based Plan Adaptation for RTS Games- 2008
Learning from Human Demonstrations for Real-Time Case-Based Planning – 2008
Situation Assessment for Plan Retrieval in RTS Games – 2009
On-Line Case based Planning – 2010

Papers adopting Evolutionary Algorithms & Dynamic Scripting:

Co-evolution in Hierarchical AI for Strategy Games – after 2004
Co-evolving Real-Time Strategy Game Playing Influence Map Trees with genetic algorithms
Improving Adaptive Game AI With Evolutionary Learning – 2004
Automatically Acquiring Domain Knowledge For Adaptive Game AI using Evolutionary Learning – 2005

Papers adopting Reinforcement Learning & Dynamic Scripting:

Concurrent Hierarchical Reinforcement Learning – 2005
Hierarchical Reinforcement Learning in Computer Games – After 2006
Goal-Directed Hierarchical Dynamic Scripting for RTS Games – 2006
Hierarchical Reinforcement Learning with Deictic repr. in a computer game- After 2006
Monte Carlo Planning in RTS Games – After 2004
Establishing an Evaluation Function for RTS games – After 2005
Learning Unit Values in Wargus Using Temporal Differences – 2005
Adaptive reinforcement learning agents in RTS games – 2008

Papers adopting Hybrid CBR/RL approaches :

Transfer Learning in Real-Time Strategy Games Using Hybrid CBR-RL – 2007
Learning continuous action models in a RTS Environment – 2008

Related Books:

AI Game Engine Programming
AI for Games

2- Developing an AI-Engine for RTS Games

We used an RTS Game Engine named “Stratagus” to develop our AI Game engine. The game that we used as a test-bed is a clone of the well-know Warcraft 2 game.

3- Maintaining the project blog

https://rtsairesearch.wordpress.com/

4- Maintaining the project repository:

• Our research stuff repository: http://rtsairesearch.googlecode.com/
• I-Strategizer (Agent’s code): http://istrategizer.googlecode.com/

5- Maintaining our own blogs:

• OmarsBrain.wordpress.com (Omar Enayet)
  
• AbdelrahmanOgail.wordpress.com (Abdelrahman Al-Ogail)
  

B- Our Next Step was publishing a paper entitled “Intelligent Online Case-Based Planning Agent Model in RTS Games” in ISDA 2010. Find it in this post.

Concerning our future plans, We are looking forward to achieve the following long-term goals:

1- Adding new theory in the area of “Simulation of Human Behavior”.
2- Developing a commercial AI Engine for RTS Games specifically and games in general. We already started and we have quite experience in game development.
3- Participate in related contests around the world for AI Engines in RTS Games (As Robocup, AAAI Starcraft Competition, ORTS Competition).
4- Initializing a major research group in Egypt in this field and become pioneers in it world wide.

However, our short term goal is enhancing the current engine , which will efficiently be able to plan and learn when playing against static AI, and use it as a test-bed to publish a number of papers , some of these papers are related to :

1- Introducing the whole Agent model and theory in AI related conference.
2- Introducing the whole AI Game Engine from a game industry point of view in a game-industry conference.
3- More Details & Testing concerning the hybridization of Online Case based Planning and Reinforcement Learning ( the topic of our last paper)
4- Knowledge representation for plans and experience in RTS games.
5- Enhancing agent’s situation assessment algorithm.
6- Comparing Case-Based Reasoning to Reinforcement Learning.

Other long-term papers’ topics include :
1- Include different planning algorithms/systems and let agent use them and make an intensive comparison between these panning systems.
2- Include different learning algorithms/systems and let agent use them and make an intensive comparison between these learning systems.
3- Multi-Agent AI : machine collaboration with other machines, or machine collaboration with human players.
4- Knowledge (Gaming Experience) Sharing.
5- Opponent Modeling.

I-Strategizer Project Documentation – Version 1.0

We’ve wrote a documentation for the last year research in a document. This documents acts a reference manual for most of our research and development. It’s considered as general orientation document for any person would like to start researching in this area. Download it from link below:

I-Strategizer Documentation Version 1.0

Intelligent Online Case-Based Planning Agent Model for Real-Time Strategy Games

Hi all,

We’ve recently published a paper titled under Intelligent Online Case-Based Planning Agent Model for Real-Time Strategy Games in 10th International Conference on Intelligent Systems Design and Application.

5-7-2010 Meeting Minutes

• Aim of meeting:
  • Starting to write a paper from the project.
• Attendants:
  • Dr. Ibrahim Fathy.
  • Omar Enayet.
  • Abdelrahman Al-Ogail.
• Below I’ll show the meeting processing.

Determination of first paper title

• We’ve found 2 suitable names:
  • Intelligent agent model for online case-based planning.
  • Extending online case-based planning with reinforcement learning.

 

Structure of the Paper

• Abstract.
• Introduction (must contain a brief info about RTS games).
• Related work:
  • Sant’s work.
  • Traditional planning work.
• Architecture.
• Agent Learning.
• Case study.
• Conclusion.

Abstract Content

• RTS domain.
• Online case-based planning problems
• Effects of this problem.
• Mentioning our contribution.

Alterations to Architecture

• Separation is required between offline and online stages.
• I-StrategizerToWargus module will be removed.
• Expert interaction is added to the environment.
• Game state will come from the world directly.
• Wargus is referred as environment.
• Replace are Cases phrase with Case phrase.
• Replace Behavior phrase with Case Behavior phrase.
• Reviser must have a separate accessing line to Casebase.
• The arrows from expansion module to current plan should be: Goal, Expanded Plan.
• The arrows from execution module to current plan should be: Plan Action, Action Feedback.
• Plan object will is replaced with Current Plan.

Tips about writing the architecture section in the paper

• Never copy from other papers; you must rephrase the words in your own way.
• Emphasize on your work “Reviser” (why and what).
• Add references as you can.
• Try to rephrase paper’s diagrams.

Future Work

• Constructing new plans online (i.e. it’s like learning from human demonstration but online).
• Retaining failed plans to predict failure.
• Revision maybe on:
  • Retrieved case only.
  • Current game history.
  • All previous games history.
• Changing my goal according to the game situation.

Situation Assessment Empirical Analysis in IStrategizer

• In this article we’ll introduce the idea of situation assessment in IStrategizer.
• Situation Assessment is a process of gathering high-level information using low-level data to help in better decision making.
• We’ll use 3 terms here:
  • Situation: is a high-level representation of the state of the world
  • Situations can be predicted based on raw features that can be directly computed from the game state, i.e. shallow features.
  • However, shallow features by themselves are not strong enough for selection of a strategy in a game. Additional derived deep features for a situation are needed.
• For example, shallow features, like the ratio of a player’s resources to that of the opponent, by themselves are less suggestive of usefulness of an appropriate strategy. However deeper features, like knowing the existence of path or a barrier between the player and its opponent, can help in choosing a rush or a tunneling strategy.
• We’ve 3 Situations:
  • Note that for each set of shallow features above we’ve a set of deep features that will help us to pick the most suitable set of plans to choose from.
  • Base Development Situation:
    • Shallow Features:
      • Basic player infrastructure is not available.
      • Advanced player infrastructure is not available.
      • Near resources for player base are not available.
      • Player has a lot of resources that are not consumed well in building the army.
    • Deep Features:
      • Basic player infrastructure is not available.
        • What’s the missing building exactly? Is it farm? Town Hall? Lumber Mill…
      • Advanced player infrastructure is not available.
        • What’s the advanced building you would to upgrade to? Get new units (i.e. dragons)? Upgrade unit attributes?
      • Near resources for player base are not available.
        • What’s the resource that is not available?
        • Where’s the proposed place to gather from?
      • Player has a lot of resources that are not consumed well in building the army.
        • What are units that you’d like to build their building more?
        • What’s the proposed direction for expanding your empire?
  • Build Army Situation:
    • Shallow Features:
      • Player has enough resources and infrastructure to construct an army.
      • Opponent is attacking/constructing the player and the player has no enough units to defend on himself.
    • Deep Features:
      • Player has enough resources and infrastructure to construct an army.
        • What’s the most available resource to construct an army?
        • From history, what are preferred units by my opponent?
        • What’s natural situation of the map (islands, no paths in between).
        • How opponent defend his base?
      • Opponent is attacking the player or constructing, army where the player has no enough units to defend on himself.
        • What are the most available resources and buildings to construct an army?
        • What are anti-units for the current opponent units?
  • Attack Situation:
    • Shallow Features:
      • Player has enough units to attack opponent.
      • Player resources are obsolete and he wants to get an opponent resources.
      • Player wants to expand his empire and enemy captures a near place.
      • Enemy is near from player base.
    • Deep Features:
      • Player has enough units to attack opponent.
        • What’s the natural of enemy’s base and current player units to utilize them for attacking? (i.e. backdoor exists, enemy doesn’t have long range units …).
      • Player resources are obsolete and he wants to get an opponent resources.
        • What’s the natural of enemy’s base and current player units to utilize them for attacking? (i.e. backdoor exists, enemy doesn’t have long range units …).
      • Player wants to expand his empire and enemy captures a near place.
        • What’s the natural of enemy’s base and current player units to utilize them for attacking? (i.e. backdoor exists, enemy doesn’t have long range units …).
      • Enemy is near from player base.
        • What’s the natural of enemy’s base and current player units to utilize them for attacking? (i.e. backdoor exists, enemy doesn’t have long range units …).
      • Here let us talk more about the deep feature used in this assessment.
        • Natural of player’s army:
          • Ranged.
          • Anti air-attack.
          • Air attack.
          • Strong units.
          • Massive number of units.
        • Natural of enemy’s base:
          • Not defended at all.
          • Has backdoors.
          • Has an air attack defense.
          • Has an anti air attack defense.
          • Has lot of units inside.
          • Has weak points (i.e. important buildings that are not defended well)
        • So, based on combination of these 2 natures we can pick a suitable attack strategy. Example:
          • Natural of player’s army: Air attack.
          • Natural of enemy’s base: has backdoors, has weak points
          • Air Attack Strategy is used!
  • Defense Situation:
    • Shallow Features:
      • Player base is not defended.
      • Enemy is attacking player or constructing an army.
    • Deep Features:
      • What’s the natural of the map duo to defending player’s base? (i.e. surrounded with wood)
      • Where are backdoors in player’s city?
      • Where are most important regions in my city?
      • From history, what are preferred units that player attack with?

Situation Assessment for Plan Retrieval in Real-Time Strategy Games

• Abstract:
  • Case-Based Planning (CBP) is an effective technique for solving planning problems that has the potential to reduce the computational complexity of the generative planning approaches. However, the success of plan execution using CBP depends highly on the selection of a correct plan; especially when the case-base of plans is extensive. In this paper we introduce the concept of a situation and explain a situation assessment algorithm which improves plan retrieval for CBP. We have applied situation assessment to our previous CBP system, Darmok, in the domain of real-time strategy games. During Darmok’s execution using situation assessment, the high-level representation of the game state i.e. situation is predicted using a decision tree based Situation- Classification model. Situation predicted is further used for the selection of relevant knowledge intensive features, which are derived from the basic representation of the game state, to compute the similarity of cases with the current problem. The feature selection performed here is knowledge based and improves the performance of similarity measurements during plan retrieval. The instantiation of the situation assessment algorithm to Darmok gave us promising results for plan retrieval within the real-time constraints.
• A Situation is a high-level representation of the state of the world. For example, in the WARGUS domain the player might be in an attacking situation, or in a base development situation, among others.
• Situations can be predicted based on raw features that can be directly computed from the game state, i.e. shallow features.
• However, shallow features by themselves are not strong enough for selection of a strategy in a game. Additional derived deep features for a situation are needed.
• For example, shallow features, like the ratio of a player’s resources to that of the opponent, by themselves are less suggestive of usefulness of an appropriate strategy. However deeper features, like knowing the existence of path or a barrier between the player and its opponent, can help in choosing a rush or a tunneling strategy.
• Situation Assessment is a process of gathering high-level information using low-level data to help in better decision making.
• Our general situation assessment technique comprises of four steps:
  • Shallow feature selection.
    
    • During this first step, a situation annotated trace is provided to a feature selection algorithm. An annotated trace consists of a sequence of world states annotated with the set of shallow features computed for each world state and the appropriate situation that world state corresponds to. This algorithm returns the set of shallow features which have high information gain. Specifically, in Darmok, we have used best-first greedy hill-climbing algorithm. For filtering the high information gain shallow features.
  • Model generation.
    
    • In this step the following three models are generated:
      • The Situation-Classification Model, , is built by providing and to a classification algorithm. This model is useful for classification of a world state to a situation using shallow features in . In Darmok, we have used a standard algorithm inducing a decision tree classifier model.
      • The Situation-Case Model, , provides a mapping from the set of situations to a subset of cases in the case-base . It can be built using statistical or empirical analysis. This model captures the intuition that not all the cases will be useful in all the situations.
      • The Situation-Deepfeature Model, , provides a mapping from to deep features in the set . This mapping is done using a feature selection algorithm or by using empirical knowledge.
  • Model execution.
    • In this third step, the models generated in the previous step are executed to get the current situation , the subset of cases from the case-base C and the subset of deep features which are most relevant to s. s is obtained by running over . Once s is known, using and , C’ and are obtained respectively.
  • Case retrieval.
    • This is the last step where using and the most similar case in retrieved from C0 using normal retrieval techniques
• Situation Assessment Working Mechanism:
  • Firstly, a subset of shallow features is selected which are used for classification of a game state into a situation.
  • Then three models:
    • For classification of game state into situations based on shallow features.
    • For mapping of situations to cases.
    • For mapping of situations to deep features respectively are generated.
• Shallow features are generally computationally inexpensive but lack the high-level inferential knowledge about the world.
• The deep features are generally computationally expensive but provide information very relevant for case selection in specific situations.

• How Situation Assessment is applied in Darmok:
  • The Offline Stage: comprising of Feature Selection and Model Generation before the game-play.
  • The Online Stage: comprising of Model Execution and Plan Retrieval during the game-play.
• We perform situation assessment in two stages since the models required for predicting the situation during Darmok’s game-play are built just once at the start. Therefore, the models can be easily generated offline using standard feature selection and classification algorithms

Architecture of Learning from Human Demonstration – 2008

• Demonstrations Triplets Extractor:
  • Input: nothing.
  • Description:
    • An expert will play the game.
    • Each time stamp a triplet will be generated. This triplet is consisted of <TimeStamp, GameState,SetOfActions>.
    • At the end of each time stamp we check if every goal was satisfied in that time stamp or not.
    • This process ends when the game ends.
  • Output:
    • A log file that contains a set D of demonstration triplets generated within the game.
• Raw Plan Extractor:
  • Input: Demonstration triplets.
  • Description:
    • Generating goal matrix, a 2D Matrix, where one of the dimensions is the set of goals, and the other dimension is the set of demonstration triplets.
    • Extracting the raw plans for each goal using the algorithm described in the paper.
    • Generate raw cases that consists of <Snippet,Episode<Goal,GameState,Outcome>>.
  • Output:
    • Raw cases.
• Ready-To-Use Cases Generator:
  • Input:
    • Raw cases.
  • Description:
    • Generate dependency graph for each snippet according to the algorithm in the paper.
    • Remove irrelevant actions.
    • Check all the plans to see if any plan P_i is a sub-plan of another plan P_j and substitute the actions in P_j that compose plan P_i with the goal of plan P_i.
  • Output: Ready-To-Use Cases.

Second Seminar Presentation

On-Line Case-Based Plan Adaptation for Real-Time Strategy Games – 2008

• Abstract:
• Traditional artificial intelligence techniques do not perform well in applications such as real-time strategy games because of the extensive search spaces which need to be explored. In addition, this exploration must be carried out on-line during performance time; it cannot be precomputed. We have developed on-line case-based planning techniques that are effective in such domains. In this paper, we extend our earlier work using ideas from traditional planning to inform the real-time adaptation of plans. In our framework, when a plan is retrieved, a plan dependency graph is inferred to capture the relations between actions in the plan. The plan is then adapted in real-time using its plan dependency graph. This allows the system to create and adapt plans in an efficient and effective manner while performing the task. The approach is evaluated using WARGUS, a well-known real-time strategy game.

• A key problem in CBP is plan adaptation;
  • Plans cannot be replayed exactly as they were stored, especially in games of the complexity of modern RTS games.
  • More specifically, CBP techniques for RTS games need adaptation techniques that are suitable for dynamic and unpredictable domains.
• Plan adaptation techniques can be classified in two categories:
  • Those adaptation techniques based on domain specific rules (domain specific, but fast)
  • Those based on domain independent search-based techniques (domain independent, but slow)
• However, most previous work on plan adaptation focus on one-shot adaptation where a single plan or set of plans are retrieved and adapted before execution. In this paper we are interested on developing domain independent and search-free plan adaptation techniques that can be interleaved with execution and that are suitable for RTS games.
• Our plan adaptation technique is based on two ideas:
  • Removing useless operations from a plan can be done by analyzing a dependency graph without performing search.
  • The insertion of new operations in the plan can be delegated to the case-base planning cycle itself, thus also getting rid of the search.
• A goal is a symbolic non-operational description of the goal, while success conditions are actual predicates that can be checked in the game state to evaluate whether a goal was satisfied or not.
• Postconditions are conditions to be expected after a behavior executes while success conditions are the conditions that when satisfied we can consider the behavior to have completed its execution
• A partial plan tree in our framework is represented as a tree consisting of two types of nodes: goals and behaviors (notice the similarity with HTN planning (Nau et al. 2005)).
• While execution, basic actions that are ready and with all its preconditions satisfied are sent to WARGUS to be executed. If the preconditions are not satisfied, the behavior is sent back to the adaptation module to see if the plan can be repaired. If it cannot, then the behavior is marked as failed.
• The plan adaptation module is divided in two submodules:
  • The parameter adaptation module.
    • The first one is in charge of adapting the parameters of the basic actions, i.e. the coordinates and specific units
  • The structural plan adaptation module.
• Plans are composed of four basic types of elements:
  • Actions:
    • Which are the basic actions that can be executed
  • Parallel plans:
    • Which consist of component plans which can be executed in parallel
  • Sequential plans:
    • Which consist of component plans which need to be executed in sequence
  • Sub-goal plans:
    • Requiring further expansion.
• We can further deduce dependencies between different plans using their preconditions and success conditions.
• We specifically consider only plans which are completely expanded and do not contain a subgoal which further needs to be expanded.
• We generate a plan dependency graph using the preconditions and success conditions of the actions. This plan dependency graph informs the plan adaptation process.
• Plan Dependency Graph Generator:
  • The plan dependency graph generation, begins by taking the success conditions of the root of the plan and finding out which of the component actions in the plan contribute to the achievement of these success conditions.
    • These actions are called direct sub-plans for the subgoal.
  • All direct sub-plans are added to the plan dependency graph.
  • Then, the plan dependency graph generator analyzes the preconditions of each of these direct sub-plans.
  • Let B₁ be an action in the plan which contributes to satisfying the preconditions of a direct sub-plan D₁. Then, it adds B₁ to the plan dependency graph and forms a directed edge from B₁ to D₁.
    • This directed edge can be considered as a dependency between B₁ and D₁.
    • This is done for each of the direct sub-plans.
  • Further this is repeated for each of the actions which are added to the graph.
  • The generation stops when there’s more nodes are added to it.
  • This process results in the formation of a plan dependency graph with directed edges between actions representing that one action contributes to the achievement of the preconditions of another action.
• However, a challenge in our work is that simple comparison of preconditions of a plan P1 with success conditions of another plan P2 is not sufficient to determine whether P2 contributes to achievement of preconditions of P1. This is because there isn’t necessarily a direct correspondence between preconditions and success.
• An example is the case where P1 has a precondition testing the existence of a single unit of a particular type. However, P2 may have a success condition testing the existence of a given number n of units of the same type. An edge should clearly be formed from P2 to P1, however a direct comparison of the conditions will not yield this relation.
• For that purpose, the plan dependency graph generation component needs a precondition-success condition matcher (ps-matcher). In our system, we have developed a rule-based ps-matcher that incorporates a collection of rules for the appropriate condition matching.
• If a dependency was not detected by our system, a necessary action in the plan might get deleted. However, if our system adds extra dependencies that do not exist the only thing that can happen is that the system ends up executing some extra actions that would not be required. Clearly, executing extra actions is better than missing some needed actions.
• The plan adaptation following the creation of the plan dependency graph has two sub-processes:
  • Elimination of unnecessary actions.
  • Insertion of extra actions.
• The first one is performed as soon as the plan is retrieved, and the second one is performed on-line as the plan executes.
• Removal of unnecessary actions:
  • Given a plan for a goal, the plan dependency graph is generated and the success conditions of each direct plan are evaluated for the game state at that point of execution.
    • This gives a list L of direct plans whose all success conditions are satisfied and hence do not need to be executed.
  • Now, consider L as the list of actions that can be removed from the plan corresponding to the plan dependency graph.
  • All actions B which are present only on paths terminating on an action D such that D L can be removed and hence can be added to L.
  • This is repeated until L becomes stable and no new plan is added to it.
  • All actions in L are removed from the plan dependency graph.
  • The resulting plan dependency graph has only those actions whose success conditions are not satisfied in the given game state and which have a path to a direct plan, also with success conditions not satisfied in the given game state.
• Adaptation for unsatisfied preconditions:
  • If the execution of an action fails because one or more of its preconditions are not satisfied, the system needs to create a game state where the given preconditions are satisfied so that the execution of the plan can proceed.
  • To enable this, the adaptation module inserts satisfying goals in the plan (one goal per unsatisfied precondition).
  • The satisfying goals are such that when plans to achieve the goals is retrieved and executed, the success of the plans implies that the preconditions of the failed action are satisfied.
  • Example: When an action P1 fails to proceed because a precondition C1 is not satisfied, a satisfying goal G1 for C1 is formed. P1 is replaced by a sequential plan containing a subgoal plan with goal G1 followed by P1.
• Notice that the plan adaptation module performs two basic operations:
  
  • Delete unnecessary actions (which is performed by an analysis of the plan dependency graph)
  • Insert additional actions needed to satisfy unsatisfied preconditions.
    • This last process is performed as collaboration between several modules:
      • The plan execution module: identifies actions that cannot be executed
      • Then, the adaptation component:
        • Identifies the failed preconditions
        • And generates goals for them
      • Finally, the plan expansion and plan retrieval modules expand the inserted goals.
• Future Work:
  • Our techniques still have several limitations. Currently, our plan adaptation techniques require a plan to be fully instantiated in order to be adapted, thus we cannot adapt plans that are still half expanded.
  • As a consequence, the high level structure of the plan cannot be adapted unless it’s fully instantiated.
    • This could be addressed by reasoning about interactions between higher level goals, by estimating which are the preconditions and success conditions of such goals by analyzing the stored plans in the case-base to achieve those goals.
  • Another line of further research is to incorporate ideas from MPA in order to be able to merge several plans into a single plan.
• This can be very useful and can increase vastly the flexibility of the approach since sometimes no single plan in the case base can achieve a goal, but a combination will.