Loading ...
Sorry, an error occurred while loading the content.

Re: Agents and GA/GP

Expand Messages
  • Russ Abbott
    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
    • 0 Attachment
      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
      Google for them.

      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
      > in an agent based model. It's about a decade
      > 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]
    • Frank Moore
      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
      • 0 Attachment
        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.,
        proportional navigation); the aircraft is controlled by your evolved
        program. Aggregate fitness is determined via simulation of several
        missile attacks. The problem get really fun when you start introducing
        uncertainty (about missile type, location, or both) and additional
        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
        > Google for them.
        >
        > 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
        > > in an agent based model. It's about a decade
        > > 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]
        >
        >
      • steve uurtamo
        ... 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
        • 0 Attachment
          > 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...
          Download and play hundreds of games for free on Yahoo! Games.
          http://games.yahoo.com/games/front
        • Frank Moore
          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
          • 0 Attachment
            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
            additional countermeasures.

            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...
            > Download and play hundreds of games for free on Yahoo! Games.
            > http://games.yahoo.com/games/front
            >


            [Non-text portions of this message have been removed]
          • I Jonyer
            ... 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
            • 0 Attachment
              -----------------------------------------------------------------------
              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

              Sponsored by the Pascal Network
              -----------------------------------------------------------------------

              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
              discussion. Each half-day will start with an invited paper for 45
              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
              the submission, including postal address, email address, telephone
              number, and fax number. Electronic versions of the final papers will
              be available on the workshop home page at www.cs.okstate.edu/cagi07/.

              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.

              Workshop home page: www.cs.okstate.edu/cagi07/
              Submit papers to: cagi07@...


              Important Dates

              Paper Submission May 7, 2007
              Acceptance Notification May 25, 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.