EPTRobustness and Plan Repair
Summary:
+ Show Spoiler +
Plan Repair is the concept of adjusting the execution of a plan in case of events negatively impacting the outcome.
Robustness describes how well a given plan is able to execute its plan in a wide range of different situations and edge cases.
Planning and Plan Repair can be applied to a lower level task of constructing e.g. a factory as well as highest level strategy.
I had written a post about planning a while ago using Prolog, a general-purpose logic programming language. An AI bot should be able to accept a goal and then derive the required steps to achieve that goal. But what happens if there are obstacles and things don’t play out the way that was anticipated?
In terms of AI research, the problem is formulated as follows:
In dynamic environments agents deal with changing situations which may partially or entirely invalidate an executable plan. Plan repair techniques aim to solve problems where modifications in the initial or goal state occur in the plan. They attempt to identify where the problem is located and fix the affected part of the plan.
The underlying assumption is that it is more efficient to repair an existing plan than to re-plan from scratch when something goes wrong.
How does this relate to Brood War? Let’s examine a seemingly simple case: The construction of a factory. What could possibly go wrong when the goal is to construct a simple building?
Well, from the perspective of a bot, the following:
- Not enough resources (mineral / gas) to build a factory
- Tech tree requirements not fulfilled (existing barracks)
- No worker available to build
- No construction site available (not enough buildable tiles, e.g. on a weird map)
- The worker gets stuck on its way to the construction site
- The worker cannot reach the construction site because of obstacles (like own or enemy units standing in the way) and just moves back and forth in a loop
- The resources aren’t available anymore by the time the worker reaches the construction site (unlike SC2, Brood War deducts the resource costs when construction is starting, not when the build command is given. The available resources can change while the worker moves to the site)
- The chosen construction site is not visible (anymore)
- The chosen construction site is not free anymore (due to own or enemy mobile units placed on it)
- The worker gets killed before it can start construction
- The worker gets killed after it starts construction but before the building is completed
- The building gets destroyed while still under construction
Furthermore, the plan itself could change because something more urgent has come up and the building is not required anymore (important scout info or resources required to defend a rush, etc.)
As you can see, there are at least 12 realistic reasons why a construction can fail. All of them need to be addressed to guarantee a successful outcome of the plan. This is where a key concept comes into play: Plan robustness.
A plan is robust if it avoids most of the potentially disadvantageous situations and there exist meaningful plan repair strategies for the remaining situations. We can divide the 12 identified issues into two categories: Green: Avoid, Red: Repair
- Not enough resources (mineral / gas) to build a factory
- Tech tree requirements not fulfilled (existing barracks)
- No worker available to build
- No construction site available (not enough buildable tiles, e.g. on a weird map)
- The worker gets stuck on its way to the construction site
- The worker cannot reach the construction site because of obstacles (like own or enemy units standing in the way) and just moves back and forth in a loop
- The resources aren’t available anymore by the time the worker reaches the construction site (unlike SC2, Brood War deducts the resource costs when construction is starting, not when the build command is given. The available resources can change while the worker moves to the site)
- The chosen construction site is not visible (anymore)
- The chosen construction site is not free anymore (due to own or enemy mobile units placed on it)
- The worker gets killed before it can start construction
- The worker gets killed after it starts construction but before the building is completed
- The building gets destroyed while still under construction
The green issues can be dealt with by a plan that is robust to begin with. That is, we only attempt to build the factory if we do have the tech tree, resources and worker available. Also, we make sure to choose a construction site that is buildable and reachable. Once we know we want to build the factory we already reserve the required resources such that they are not available to be used for anything else until they are actually spent.
Green issues mostly require thoughtful programming and consideration of edge cases. Thereby we can prevent the issues from occurring already before we start executing the plan.
The red issues however cannot be avoided because they might occur outside of our control. Even with careful and robust planning we cannot avoid death of a worker due to attacking enemies or the game engine failing its path finding resulting in a stuck worker.
Red issues require detection and appropriate repair measures while the plan is executed. They are more challenging to address than green issues.
Let’s assume the worker gets killed on its way to the construction site. How do we deal with this? Just send another one? Choose a different construction site? What if the second one gets killed as well? Should we escort the worker with army units? What if we don’t have any army units?
Likely it’s too late to react when the worker is dead anyways. Instead we should probably react when it gets attacked?
Experienced humans can intuitively decide what issues are likely to occur and how to deal with them. If a drone attacks the SCV we know we can send another SCV to fend it off, but if confronted with 2 enemy zealots we wouldn’t do that.
Teaching the bot to plan repair
One way to teach a bot plan repair is to create a large number of rules in an attempt to deal with any situation imaginable. But of course, this is not interesting from an AI perspective, since we basically just hardcode human expertise. Much more interesting would be a system that finds such rules by itself. For example, it could take note of all events that occur in a game and attempt to associate them with plan failure over many games.
Simplified, it could reach the following conclusion:
- Sometimes, when a drone shows up, the plan fails
- If no drone shows up, the plan never fails
Now it could attempt to take random measures whenever a negatively connoted event occurs and again take note of the outcomes and reach the following conclusion:
- When a drone shows up and I halt construction the plan still fails
- When a drone shows up and I send an SCV to attack it sometimes the plan executes successfully
- If I not only send an SCV to attack, but also retreat the first SCV before it is killed and resume construction with the second one, then the plan almost always succeeds
It can also attempt to associate its own actions with negatively connoted events as follows:
- If I place my building towards the enemy a drone is more likely to show up (bad)
- If I place my building hidden in the back of my base a drone is less likely to show up (good)
This way it will learn to prevent bad events in the first place.
Taking it to the next level
The concept of plan and plan repair can be applied to all levels of strategy as well.
In the most extreme case, achieving the goal of the game can be formulated as a plan to walk over and destroy the enemy townhall (the game is over when one party has 0 buildings). Anything preventing the bot from doing this can be interpreted as an event negatively impacting the outcome, to be dealt with via plan repair:
- Enemy builds additional buildings? Adjust plan to destroy them as well
- Enemy builds buildings faster than I can destroy them? Train a larger army
- Enemy trains army to defend its buildings? Adjust plan to deal with army first, such that the buildings can be destroyed afterwards
- Enemy attacks my army before it can destroy the buildings? Create a sub-plan to fend off the enemy attack first before proceeding with the main plan
Further reading
Plan repair techniques are being researched in the field of artificial intelligence.
For example, this article provides a formal definition for the multi-agent plan repair problem:
Antonín Komenda, Peter Novák, Michal Pechoucek:
Decentralized Multi-agent Plan Repair in Dynamic Environments.
The following simple visualization is taken from
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.520.2647&rep=rep1&type=pdf
![[image loading]](https://i.imgur.com/qx4eICY.png)
Disclaimer
Unlike other concepts described in this blog, I have not implemented or tested any of the above behavior yet. As of now, the approach is purely theoretical.
I am aware that the descriptions are very high-level.
