Browse Groups

• First of all I apologize for the misleading subject. I recycled a previous message. As Simon says, it is predator/prey in which one side (in this case the
Message 1 of 5 , Jan 24, 2007
View Source
First of all I apologize for the misleading subject. I recycled a previous
message.

As Simon says, it is predator/prey in which one side (in this case the
prey) is smart (uses a GA/GP dynamically during the chase) and the other has
some other useful quality. I'll check out Differential Games.

To answer Bob's question, there is not a population of boats. The (single)
boat (the prey) uses a GA to determine its next move at each time step. It's
not quite the same as saying there is a population of scenarios. There is a
single time-stepped agent-based model. As the model runs at each time step
the boat determines it next move by simulating possible futures (that's
where the populations come in) and choosing the best one.

-- Russ

from "Lucas, Simon M" <sml@...> There are many possible
variations on this theme -
prey / predator(s) problems were explored analytically
by Rufus Isaacs in his work on Differential Games,
and many others experimentally since then.

The proposed solution is a *bit* similar to Monte Carlo
approach to playing Go, and a very similar method has
been used by Evan Hughes to play checkers.

I don't have the exact references to hand - you'll have to

Best regards,

Simon Lucas

________________________________

From: genetic_programming@yahoogroups.com<genetic_programming%40yahoogroups.com>
[mailto:genetic_programming@yahoogroups.com<genetic_programming%40yahoogroups.com>]
On Behalf Of Bob MacCallum
Sent: 24 January 2007 08:56
To: genetic_programming@yahoogroups.com<genetic_programming%40yahoogroups.com>
Subject: {Disarmed} Re: [GP] Re: GA and Sudoku

so I just want to be clear (too lazy to follow the link): there isn't a
population of boats, instead the boat has a population of scenarios and
chooses the best one?

On 1/24/07, Russ Abbott <Russ.Abbott@... <Russ.Abbott%40gmail.com>
<mailto:Russ.Abbott%40gmail.com> > wrote:
>
> Hi All,
>
> I recently came across this example
> < https://netfiles.uiuc.edu/wdavis1/www/
<https://netfiles.uiuc.edu/wdavis1/www/> >of using a genetic algorithm
> old and was apparently assigned as a student homework exercise.
Briefly,
> it's a simulation of boat being chased by a fleet of torpedoes. (You
can
> think of the boat and the torpedoes as agents in a simple agent-based
> world.) The boat is safe if it reaches its home base without getting
hit.
> The boat is slower but more maneuverable than the torpedoes.
>
> Apparently the boat uses a GA to plot its course. At each time step it
> does
> something like select the best 20 step move sequence and take the
first
> step. The torpedoes are stupid. At each time step they turn in the
> direction of the boat to the extent that they can. Because the
torpedoes
> are so stupid and deterministic, the boat can simulate them perfectly
in
> its
> GA.
>
> Has anyone seen this or anything like it? Does anyone know of similar
> work?
>
> -- Russ

[Non-text portions of this message have been removed]
• Hello all. Russ s boat problem is remarkably similar to what I did for my dissertation in 1997. In my problem, a single simulated aircraft (e.g., F-16) can be
Message 2 of 5 , Jan 24, 2007
View Source
Hello all.

Russ's boat problem is remarkably similar to what I did for my
dissertation in 1997. In my problem, a single simulated aircraft (e.g.,
F-16) can be shot at by one or more surface-launched anti-aircraft
missiles (e.g., SA-15s). How does one use genetic programming to evolve
a control program that, when executed during each of a series of
simulated time steps (e.g., once every 0.02 seconds), maximizes the
survivability of the aircraft? The missiles are faster and more agile,
and controlled by a hard-wired and deadly guidance strategy (e.g.,
program. Aggregate fitness is determined via simulation of several
missile attacks. The problem get really fun when you start introducing
countermeasures, and when you move from 2D to 3D.

Not surprisingly, there are many great references from this much-studied
field: in addition to Isaacs, look at Krasovskii and Subbotin (1988),
Grimm and Well (1990), Grefenstette, Ramsey, and Schultz (1990), Shinar
and Steinberg (1977), Barron (1995), Basar and Olsder (1982), Smith and
Dike (1997), etc. Game-theoretic, control-theoretic, and even GA-based
solutions to very many predator/prey problems are available.

Possibly the best publicly available paper I wrote on the subject
appeared in "Evolutionary Computation, 10(2): 129-149 (Summer 2002)",
from MIT Press. I found that by eliminating constraints required by
analytical solutions and simply letting evolution do its job, the GP
evolved a reactive control strategy that dramatically improved the
aircraft's chances: in terms of survivability, my evolved solutions beat
the socks off of analytic/control-theoretic/game-theoretic solutions
available to me at that time. I expect that the same type of result may
occur in your study of boats. Of course, the more realistic your
simulations, the more relevant your solutions will be to real-world
problems.

-- Frank

Russ Abbott wrote:
>
>
> First of all I apologize for the misleading subject. I recycled a previous
> message.
>
> As Simon says, it is predator/prey in which one side (in this case the
> prey) is smart (uses a GA/GP dynamically during the chase) and the other has
> some other useful quality. I'll check out Differential Games.
>
> To answer Bob's question, there is not a population of boats. The (single)
> boat (the prey) uses a GA to determine its next move at each time step. It's
> not quite the same as saying there is a population of scenarios. There is a
> single time-stepped agent-based model. As the model runs at each time step
> the boat determines it next move by simulating possible futures (that's
> where the populations come in) and choosing the best one.
>
> -- Russ
>
> from "Lucas, Simon M" <sml@... <mailto:sml%40essex.ac.uk>> There
> are many possible
> variations on this theme -
> prey / predator(s) problems were explored analytically
> by Rufus Isaacs in his work on Differential Games,
> and many others experimentally since then.
>
> The proposed solution is a *bit* similar to Monte Carlo
> approach to playing Go, and a very similar method has
> been used by Evan Hughes to play checkers.
>
> I don't have the exact references to hand - you'll have to
>
> Best regards,
>
> Simon Lucas
>
> ________________________________
>
> From: genetic_programming@yahoogroups.com
> <mailto:genetic_programming%40yahoogroups.com><genetic_programming%40yahoogroups.com>
> [mailto:genetic_programming@yahoogroups.com
> <mailto:genetic_programming%40yahoogroups.com><genetic_programming%40yahoogroups.com>]
> On Behalf Of Bob MacCallum
> Sent: 24 January 2007 08:56
> To: genetic_programming@yahoogroups.com
> <mailto:genetic_programming%40yahoogroups.com><genetic_programming%40yahoogroups.com>
> Subject: {Disarmed} Re: [GP] Re: GA and Sudoku
>
> so I just want to be clear (too lazy to follow the link): there isn't a
> population of boats, instead the boat has a population of scenarios and
> chooses the best one?
>
> On 1/24/07, Russ Abbott <Russ.Abbott@...
> <mailto:Russ.Abbott%40gmail.com> <Russ.Abbott%40gmail.com>
> <mailto:Russ.Abbott%40gmail.com> > wrote:
> >
> > Hi All,
> >
> > I recently came across this example
> > < https://netfiles.uiuc.edu/wdavis1/www/
> <https://netfiles.uiuc.edu/wdavis1/www/>
> <https://netfiles.uiuc.edu/wdavis1/www/
> <https://netfiles.uiuc.edu/wdavis1/www/>> >of using a genetic algorithm
> > old and was apparently assigned as a student homework exercise.
> Briefly,
> > it's a simulation of boat being chased by a fleet of torpedoes. (You
> can
> > think of the boat and the torpedoes as agents in a simple agent-based
> > world.) The boat is safe if it reaches its home base without getting
> hit.
> > The boat is slower but more maneuverable than the torpedoes.
> >
> > Apparently the boat uses a GA to plot its course. At each time step it
> > does
> > something like select the best 20 step move sequence and take the
> first
> > step. The torpedoes are stupid. At each time step they turn in the
> > direction of the boat to the extent that they can. Because the
> torpedoes
> > are so stupid and deterministic, the boat can simulate them perfectly
> in
> > its
> > GA.
> >
> > Has anyone seen this or anything like it? Does anyone know of similar
> > work?
> >
> > -- Russ
>
> [Non-text portions of this message have been removed]
>
>
• ... can you give an example? i m presuming that you don t mean constraints related to the motion or physical limitations of the aircraft. s.
Message 3 of 5 , Jan 24, 2007
View Source
> I found that by eliminating constraints required by
> analytical solutions and simply letting evolution do its job, the GP
> evolved a reactive control strategy that dramatically improved the
> aircraft's chances:

can you give an example? i'm presuming that you don't mean
constraints related to the motion or physical limitations of the
aircraft.

s.

____________________________________________________________________________________
Bored stiff? Loosen up...
http://games.yahoo.com/games/front
• Steve, you bring up an interesting issue. For many problems (for example, optimal control problems), if can be extremely difficult to derive a closed-form
Message 4 of 5 , Jan 26, 2007
View Source
Steve, you bring up an interesting issue. For many problems (for
example, optimal control problems), if can be extremely difficult to
derive a closed-form solution. The usual alternative is to make
assumptions that simplify the model enough to allow an analytical
solution to be developed. When I was studying the missile avoidance
problem, most of the textbook solutions I saw made unrealistic
assumptions (e.g., the missile and aircraft are traveling in a 2D
space, the missile is traveling at constant speed, the missile's
control laws are known to the aircraft, the missile's location is
precisely available to the aircraft, etc.). In addition, they did not
model uncertainty well at all, and could not incorporate the use of

On the other hand, an evolutionary system that uses a high-fidelity
simulator to evolve optimal strategies doesn't care about such
restrictions. Of course, it still needs to account for other
constraints, such as the physical model -- i.e., an aircraft that
attempts to pull 35Gs should be given a pretty low fitness value! So,
your assumption (below) is exactly correct.

To elaborate slightly: the classic 2D analytical solution to maximize
miss distance between an aircraft and a pursuing missile utilizing a
specific set of guidance parameters might have the aircraft make three
precisely timed turns. (See Zarchan 1992.) But the GP solution might
(for example) incorporate accelerations with turns to increase miss
distance. Further, the GP solution is easily extended to allow the
aircraft to utilize chaff/flares, jamming, altitude advantages, etc. --
something that cannot be said for the analytical solutions I've
seen. The result I saw was an improvement in predicted survivability
from something like 86% to 98%. I'm going to guess that there are a
fairly large number of problems for which GPs -- using accurate
simulations for fitness evaluation -- could evolve better control
strategies than those used today. Hope this helps!

----- Original Message -----
From: steve uurtamo <apoxonpoo@...>
Date: Wednesday, January 24, 2007 1:05 pm
Subject: Re: [GP] Re: Agents and GA/GP

> > I found that by eliminating constraints required by
> > analytical solutions and simply letting evolution do its job,
> the GP
> > evolved a reactive control strategy that dramatically improved
> the
> > aircraft's chances:
>
> can you give an example? i'm presuming that you don't mean
> constraints related to the motion or physical limitations of the
> aircraft.
>
> s.
>
>
>
>
>
>
>
_______________________________________________________________________
_____________
> Bored stiff? Loosen up...
> http://games.yahoo.com/games/front
>

[Non-text portions of this message have been removed]
• ... Call for participation ICML-2007 Workshop on Challenges and Applications of Grammar Induction In conjunction with the International Conference on Machine
Message 5 of 5 , Mar 30, 2007
View Source
-----------------------------------------------------------------------
Call for participation
ICML-2007 Workshop on
Challenges and Applications of Grammar Induction

In conjunction with the International Conference on Machine Learning,
Oregon State University, June 20 - June 24, 2007

-----------------------------------------------------------------------

Description

Grammar Induction (GI), also known as Grammatical Inference, is about
learning grammars from data. A well-known important application of GI
is natural language learning, but it is applicable in a much broader
sense to the problem of learning structural models from data. The data
typically consists of sequences of discrete events from various domains
(such as text, DNA fragments, primary structure of proteins, sequential
process log-files and musical scores), but can also include trees and
arbitrary graphs (such as metabolic networks and social networks).
Typical models include formal grammars (regular, context-free, context-
sensitive, . . .), and statistical models in related formalisms such as
probabilistic automata, hidden Markov models, probabilistic transducers
or conditional random fields.

The CAGI workshop aims at highlighting current challenges in grammar
induction with a special focus on applicability issues including:
- practical evaluations demonstrating the usefulness of the proposed
techniques,
- novel applications of grammar induction algorithms,
- noise resistant approaches,
- semi-supervised grammar learning,
- learning from partial sequences or streams,
- approximate induction and model optimization,
- experimental assessments illustrating the current limit(s) of the GI
field,
- practical complexity and scalability issues (alphabet size, noise
level, data sparseness, data inconsistency, . . .),
- evaluation of similarity learning algorithms from structured data
(pair-HMM learning, stochastic transducer learning, . . .).

Workshop Format

The workshop will include presentations of peer-reviewed papers. Each
such paper will be assigned 30 minutes, including 10 minutes for
minutes including the discussion. The day will be concluded with an
open panel for discussing the key lessons learned and pointing at
relevant research perspectives.

Submission Information

Prospective authors are invited to email their 8-page papers to
cagi07@... by the due date in PDF format. Formatting
instructions are given by the conference at
http://oregonstate.edu/conferences/icml2007/icml_format_2007.zip.
The workshop will not have a blind review process, and therefore
author names, affiliations, and contact information should appear in
number, and fax number. Electronic versions of the final papers will

Interested participants are also invited to submit 2-page position
papers. These will also be peer-reviewed and appear in the workshop
proceedings. If the workshop schedule allows, short presentations
at the end of the day may be possible as well.

Submit papers to: cagi07@...

Important Dates

Paper Submission May 7, 2007
Electronic Proceedings June 15, 2007
Workshop date June 24, 2007

Organizing Committee

Istvan Jonyer, Oklahoma State University, USA
Pierre Dupont, Universit� catholique de Louvain, Belgium
Tim Oates, University of Maryland Baltimore County, USA
Marc Sebban, Universit� de Saint-Etienne, France

Program Committee

Pierre Dupont (PC chair), Universit� catholique de Louvain, Belgium
Pieter Adriaans, Universiteit van Amsterdam, The Netherlands
Vasant Honavar, Iowa State University, USA
Istvan Jonyer, Oklahoma State University, USA
Laurent Miclet, Universit� de Rennes, France
Tim Oates, University of Maryland Baltimore County, USA
Rajesh Pareck, Iowa State University, USA
Yasubumi Sakakibara, Keio University, Japan
Marc Sebban, Universit� de Saint-Etienne, France
Menno van Zannen, Macquarie University, Australia
Enrique Vidal, Universidad Polit�cnica de Valencia, Spain

_________________________________________________________________
Live Search Maps � find all the local information you need, right when you
need it. http://maps.live.com/?icid=hmtag2&FORM=MGAC01
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.