Adaptive AI Engine for RTS Games

Discussing the theory and practice

Introducing – “On-line Planning for Resource Production in RTS”

Posted by ferasferas on October 31, 2010

On-line Planning for Resource Production in Real-Time Strategy Games

Hei Chan, Alan Fern, Soumya Ray, Nick Wilson and Chris Ventura

School of Electrical Engineering and Computer Science

Oregon State University

Corvallis, OR 97330

{chanhe,afern,sray,wilsonic,ventura}@eecs.oregonstate.edu

Goal :

Develop action-selection mechanism in producing certain amount of resources as fast as possible.

Planner :

Computationally efficient “action-selection” mechanism which at each epoch creates a possibly Sub-Optimal concurrent plan from the current state to the goal, then begin executing the set of initial actions.

How it’s done :

formed via a combination of MEA(means-ends-analysis) and Scheduling and Bounded Search over sub-goals that aren’t required for goal achievements but may improve the make span.

Two Key problem domains :

-Resource production and tactical battles.

In Resource Production : player has to produce ( or gather ) varies raw materials, buildings, civilian and military Units to improve their economic and military power.

Tactical Battles : a player uses military units to gain territory and defeat enemy Units ( offensive or defensive actions ).

“Winning the Resource Production race is often a key factor in overall success”.

Uses :

1- either in computer opponent A.I.

2- Human can use it to specify resources needed and the Planner will get the best way to get this “RTS resource production is interesting from a pure A.I. Planning perspective as it encompasses a number of challenging issues”.

First, resource production involves temporal actions with numeric effects.

Second, performing well in this task requires highly concurrent activity.

Third, real-time constraints of the problem require action selection be computational efficient in apractical sense.

Why? :

Most existing planners are :

1- not handling temporal and numerical domains.

2- simply too inefficient to be useful.

3- produce highly Sub-Optimal plans.

The planning component used by online planner is based on a combination of means-ends analysis (MEA) and scheduling.

Given an initial state and resource goal, is used to compute a sequential plan that reaches the goal using the minimum number of actions and resources in sense that any valid plan must include all of the actions in the MEA plan.

Importantly, the special structure of our domain guarantees that MEA will produce such a plan and do so efficiently (linear time in the plan length).

Given the minimum sequential plan, we then reschedule those actions, allowing for concurrency, in an attempt to minimize the make span. This scheduling step is computationally hard, however, we have found that simple worst-case quadratic time heuristic methods work quite well. Thus both the MEA step and scheduling step are both low-order polynomial operations in the minimum number of actions required to achieve the goal, allowing for real-time efficiency.

Refrences :

MEA( means-ends analysis) : http://en.wikipedia.org/wiki/Means-ends_analysis

Advertisements

3 Responses to “Introducing – “On-line Planning for Resource Production in RTS””

  1. ZiKaS said

    Feras, I’ve got couple of questions:
    1. Are Tactical Battles included in the resource production planner? And if yes, how the planner is restricted to resource production? By this it’s also concerned with other strategical issues.
    2. What’s meant by Numeric Effects?

  2. ferasferas said

    1- Are Tactical Battles included in the resource production planner? And if yes, how the planner is restricted to resource production? By this it’s also concerned with other strategical issues.

    No, the paper defines two key problems in the Domain of RTS games planing and then the author talks about focusing in the misson of making an action-selection mechanism in Resource Production.

    —————————
    2. What’s meant by Numeric Effects?

    Resource Production can be either a Producer or Consumer. you are a producer e.g. when you send your “Peasant” and gather some Raw material resources for you and on the contrary you are a consumer e.g. when you build a barracks or train a foot-men which consumes some of your raw materials.

    The numeric effect on planning here is:

    a- How Many Peasants Should i train where the difference in number will affect the current resources and the resources that will be gathered after their work ?

    b- Should i send the Peasant to gather me the required gold or should i Send him Gather Wood then Build a Farm and Train other peasants to Work with him ?

    The numeric nature of the planning problem in Resource Production is that it’s affected by certain resources and how to get a Certain NUMBER of them.

    (Resources = raw Materials, Building, civilian, military units).

  3. ZiKaS said

    Thanks dude, I got answers.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: