Games we'd like to play...
The title for the Marine game is: Deep space Attack
The Storyline is: In the deep realms of space, an evil so powerful has
just awoken. The evil is powerful enough to destroy the hole galaxy......
who is going to do this? As he walks to the main office, John the Space
Marine and the chief go up to the office.
The chief sits down and says,
"The Set Covering Deployment
Problem could be an invaluable aid in
positioning your Space Marine units."
John smiles and replies, "Yes, the Set covering deployment seeks an optimal
stationing of Marine troops in a set of space regions so that a relatively
small number of Marine troop units can control a large space region."
The Chief continues,
"The Set covering deployment can be mathematically formulated as a
(0,1)-integer programming problem. Integer programming is a special case of
linear programming, which refers to optimizing an outcome based on some set
of constraints using a linear mathematical model, and (0,1)-integer
programming means that all variables are required to be integers equal to
either 0 or 1--in other words, the variables are binary.
To formulate your Powerful Evil domination problem, consider the 8
provinces of the Powerful Evil Empire illustrated on this chart. Each
region is represented as a white disk, and the red lines indicate region
connections. Call a region secured if one or more field Marines are
stationed in that region, and call a region securable if a field Marine can
be deployed to that area from an adjacent area. In addition, assume that a
field Marine can only be deployed to an adjacent region if at least one
Marine remains in the original region to provide logistical support. Also
assume that each region contains at most two Marines , as the number of
available Marines are limited and cannot be concentrated in any one region.
This problem can then be mathematically formulated by representing the
Powerful Evil area as a graph.
We can then associate two binary variables and with each vertex (i.e.,
each province) in the vertex set of the Powerful Evil Empire graph which
specify whether a first and second field Marine (respectively) is located
at a given vertex .
In the terminology of graph theory, the Powerful Evil Empire graph is a
simple connected graph on eight vertices and with 13 edges.
In set covering deployment, the problem to be solved is to maximize the
quantity subject to the constraints
which guarantees that the first Marine is stationed at a given vertex
before a second can be,
which guarantees that if does not contain a field Marine , it has a
neighbor with two field Marines, and
which enforces the integer constraint (i.e., when combined with the first
constraint, only zero, one, or two field Marines may be placed in any given
region). This integer programming problem can then be translated into matrix
terms and solved using standard techniques to find the minimum number of
field Marines needed to secure the Powerful Evil Empire.
John shakes his head in amazement.
the Chief continues
In the case of Marine officers in Space, to first approximation (ignoring
local topography such as planets, stars etc.) we can assume that each
officer "covers" a circular region (i.e., a disk) whose size is proportional
to the distance that officer can see (or travel). Taking the search region
as a square set of space sectors (shown in gray below), the following
visualization shows a configuration of randomly distributed Marines officers
with random coverage radii, giving an arrangement that covers only 50% of
the search region.
Obviously, the larger the size of the Marines force and the larger the
coverage radii of individual Marines units, the higher the fraction of area
that can be covered. However, optimal placement gives the best coverage
possible for a fixed set of Marines units. In the case above, it turns out
to be possible to arrange the six disks so that they have no overlap, so the
maximum coverage is given by , i.e., the sum of the disk areas, each of
which is given by times the radius squared, where radii are measured in
units of the edge length of the square.
In general, achieving optimal coverage requires minimizing disk overlap, as
well as minimizing the amount by which disks extend outside the area of
surveillance. As you can see below, an optimal solution is not necessarily
unique; in this case, there are several separate disk arrangements that all
share an optimal 69% coverage. You can interactively explore optimal
coverages for different numbers of Marines units.
Spatial optimization
Covering problems are a form of Spatial optimization problem. In general,
such problems are difficult to solve even approximately, let alone exactly.
In the more complicated case of placing even as many as ten Marines, one can
imagine moving them around "by hand." But in general, as the number of
Marines becomes large, problems of this type become unmanageable using not
only "hand" methods, but also using any sort of combinatorial methods.
Effective practical methods are thus needed."
John replies,
in the case of Powerful Evil domineering space, addressing a problem
mathematically generally requires two steps: (1) formulating the problem
mathematically and (2) using appropriate methods to find a solution.
Depending on the nature of the problem, one of these steps may be harder
than the other. In the idealized Marines deployment problem, step 1 is
"easy," as the problem can be rather succinctly formulated as maximizing the
function
--that is, finding the set of points constrained to the unit square () that
give , where is the Iverson bracket, denotes a vector norm, and ? is the
logical OR operator. Here, we have made the assumptions that a given Marines
officer's covering radius is fixed regardless of the officer's position,
and that we know or can estimate a value of this radius for each Marines
officer. Finally, the double integral over the unit square that gives the
total amount of area covered by Marines. So the mathematical formulation
simply says, "For a given set of Marines positions and coverage radii, find
all regions in the unit square covered by at least one Marines officer, sum
their areas (making sure to count regions of overlap only once), and
maximize this area for fixed radii over all possible Marines positions."
Once the problem has been mathematically formulated, it can be solved using
one of a number of optimization algorithms.
John smiles and says that will certainly solve where the Powerful Evil is
and how to destroy it with the minimum number of Marines!
As John leaves, the game begins!
---
Gamers mailing list __ [email protected]
If you want to leave the list, send E-mail to [EMAIL PROTECTED]
You can make changes or update your subscription via the web, at
http://audyssey.org/mailman/listinfo/gamers_audyssey.org.
All messages are archived and can be searched and read at
http://www.mail-archive.com/[EMAIL PROTECTED]
If you have any questions or concerns regarding the management of the list,
please send E-mail to [EMAIL PROTECTED]
