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

Re: [neat] Re: Any recommended reading on combining novelty search and competitive coevolution?

Expand Messages
  • Drew Kirkpatrick
    Ken, I think I get what you re saying about categorizing parasites (or, their behavior) into classes. I m thinking in particular about the robot duel from your
    Message 1 of 10 , Jun 1, 2011
      Ken,

      I think I get what you're saying about categorizing parasites (or, their behavior) into classes. I'm thinking in particular about the robot duel from your paper "Competitive Coevolution through Evolutionary Complexification". Instead of categorizing the parasite behavior, I was thinking break out meaningful classifications of sensor inputs. Classification of behavior of the host would based on it's movement vector and speed (moving away, towards, fast/slow, going after food, etc). Of course, this is a dynamic environment. 

      So for each time the classification of inputs changes, the behavior of the host is classified and checked for novelty. These individual novelty measurements are all added up at the end of the run, and divided by the number of class of input changes to normalize things. 

      Still spit-balling here.

      As far as making it real "competitive coevolution", of course a record of who won is essentially a fitness measure, so there'd have to be a hybrid novelty/fitness in there somewhere, because measuring who won is not a novelty measure. 

      I still think novelty search brings a lot of benefits to the table. My current spit-ball is that there is an added parameter for population growth allowance for the host group. Instead of a fitness function, a novelty metric is used (assuming one can be made, obviously that's tricky). The host population remains the hosts until their population has grown the specified amount. I'm hoping that will encourage a nice broad range of strategies to be evaluated. Once that max population % has been hit, a "cataclysmic event" occurs (cataclysm-neat? rapture-neat? Harold Camping-neat?)  to wipe out the extra population, and only the best performing hosts are kept, which would be how it integrates into the competition side of things. . 

      Then the parasites and hosts flip. Essentially novelty is used to explore differing behaviors up until the cataclysmic event, then performance is used to prune the population back down, and give the "other team" their go. 

      Not sure if there would be any benefit to such an approach, but if I can figure out a means of quantifying the novelty, I'm gonna give it a whirl. Gotta write up something interesting to graduate I suppose. 

      Any thoughts would be greatly appreciated. 

      -Drew

      On Sat, May 28, 2011 at 5:59 PM, Ken <kstanley@...> wrote:
       



      Hi Drew, I just wanted to echo that I think combining novelty search with interaction between evolving agents is very interesting, if only we can find a way to characterize behavior generally enough to overcome the inherent noisiness of interaction. Of course, you have clearly been thinking about that, and it may be possible to make progress following your line of reasoning. Maybe if parasites could be categorized into classes and novelty was a concatenation of behaviors across all known classes it could make more sense of the behavior space than just a raw behavior characterization. I'm sure there are many other ways to think about it too.

      One other thing to note is that it may not really be "competitive" coevolution per se if you implemented such an experiment. If novelty is the driving force, it's not clearly competitive or cooperative, which of course is perfectly fine in any case.

      ken



      --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@...> wrote:
      >
      > Joel,
      >
      > Thanks for the feedback. I was just thinking how difficult the problem would
      > be with the parasite agents doing things differently each time. Thus the
      > novelty metric would have to encompass the novel behavior relative to what
      > the parasite did.
      >
      > Another random thought is that if you could automate recognition of the
      > differing behaviors/techniques of the parasite, and develop a completely
      > different novelty search for just that one type parasitic behavior. Thus you
      > end up with a large modular NN, with each module being a novelty search
      > generated NN developed to handle that particular type of technique/behavior
      > of the parasite. A higher level NN would handle recognition of the
      > parasite's behavior, and select the appropriate NN module to use against the
      > parasite in that instance. I think I spotted some papers floating about on
      > automatic decomposition of problems, maybe that can feed into such random
      > thinking.
      >
      > Not a well formed thought as of yet, but it's always good to type out brain
      > farts.
      >
      >
      > -Drew
      >
      > On Fri, May 27, 2011 at 2:28 PM, joel278 <lehman.154@...> wrote:
      >
      > >
      > >
      > > Hi Drew,
      > >
      > > As far as I know, competitive coevolution and novelty search have not yet
      > > been combined in any publications. Ken and I have had some discussions about
      > > possible ways to do it in the past, but haven't done any experiments.
      > >
      > > The main complication when combining both techniques is that the behavior
      > > of a particular individual is no longer statically well-defined in
      > > coevolution, but is dependent on what individual(s) it is evaluated with.
      > > For example, the board states that a checkers-playing agent proceeds through
      > > depends on its opponent.
      > >
      > > A similar issue would arise when applying novelty search in a noisy
      > > environment; its behavior might then be probabilistic. You could do multiple
      > > evaluations and have a behavioral characterization that is related to the
      > > distribution of behaviors. Alternatively, novelty search might be robust
      > > enough that nothing special needs to be done.
      > >
      > > This direction of research is very interesting though, and I hope that you
      > > follow up on it. I think it is particularly promising if done right because
      > > competitive coevolution is a potential a path to open-ended evolution (e.g.
      > > the red queen hypothesis). However, in practice coevolution is subject to
      > > coevolutionary forms of "deceptive local optima" (e.g. mediocre stable
      > > states, disengagement ,etc.) which novelty search has proved effective with
      > > dealing with in other non coevolutionary domains.
      > >
      > > Joel
      > >
      > >
      > > --- In neat@yahoogroups.com, "ze_dakster" <drew.kirkpatrick@> wrote:
      > > >
      > > > I'm curious about merging novelty search with competitive coevolution,
      > > and haven't been able to find any papers describing such an undertaking yet.
      > > Anyone aware of any papers covering that topic?
      > > >
      > > > Much thanks in advance for any tips.
      > > >
      > >
      > >
      > >
      >


    • Ken
      Hi Drew, I understand the basic idea you have. It does sound like you have a workable idea for integrating novelty search into competitive coevolution. Of
      Message 2 of 10 , Jun 9, 2011
        Hi Drew, I understand the basic idea you have. It does sound like you have a workable idea for integrating novelty search into competitive coevolution. Of course, I'd be particularly careful on the way behavior is measured because it is the key to identifying novelty. One tip is to make sure you don't only include raw outputs or raw inputs as part of the behavior characterization, because what matters most is what an agent actually does, as opposed to what it wants to do. For example, if an agent spend 100 timesteps trying to run through a wall, we would want to characterize its behavior as being stalled rather than as moving forward.

        Also, one of the big challenges in competitive coevolution (and alife in general) is to create a domain that is open-ended enough to support something interesting arising. The robot duel was my attempt to do that, but perhaps it could be enhanced to support more open-endedness, though I don't know how off-hand. But the risk you always have in these domains is that even if you have a fantastic algorithmic setup that in principle could discover amazing behaviors, it is always possible that the domain itself only supports a limited range of strategies. For example, it is hard to imagine strategies in the robot duel that go very far beyond the one shown here:

        http://www.cs.utexas.edu/users/nn/pages/research/robotmovies/clip8.gif

        In any case, overall I think your idea can make a good experiment. You mention that you need to write something up for graduation - what degree are you working on?

        ken

        --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@...> wrote:
        >
        > Ken,
        >
        > I think I get what you're saying about categorizing parasites (or, their
        > behavior) into classes. I'm thinking in particular about the robot duel from
        > your paper "Competitive Coevolution through Evolutionary Complexification".
        > Instead of categorizing the parasite behavior, I was thinking break out
        > meaningful classifications of sensor inputs. Classification of behavior of
        > the host would based on it's movement vector and speed (moving away,
        > towards, fast/slow, going after food, etc). Of course, this is a dynamic
        > environment.
        >
        > So for each time the classification of inputs changes, the behavior of the
        > host is classified and checked for novelty. These individual novelty
        > measurements are all added up at the end of the run, and divided by the
        > number of class of input changes to normalize things.
        >
        > Still spit-balling here.
        >
        > As far as making it real "competitive coevolution", of course a record of
        > who won is essentially a fitness measure, so there'd have to be a hybrid
        > novelty/fitness in there somewhere, because measuring who won is not a
        > novelty measure.
        >
        > I still think novelty search brings a lot of benefits to the table. My
        > current spit-ball is that there is an added parameter for population growth
        > allowance for the host group. Instead of a fitness function, a novelty
        > metric is used (assuming one can be made, obviously that's tricky). The host
        > population remains the hosts until their population has grown the specified
        > amount. I'm hoping that will encourage a nice broad range of strategies to
        > be evaluated. Once that max population % has been hit, a "cataclysmic event"
        > occurs (cataclysm-neat? rapture-neat? Harold Camping-neat?) to wipe out the
        > extra population, and only the best performing hosts are kept, which would
        > be how it integrates into the competition side of things. .
        >
        > Then the parasites and hosts flip. Essentially novelty is used to explore
        > differing behaviors up until the cataclysmic event, then performance is used
        > to prune the population back down, and give the "other team" their go.
        >
        > Not sure if there would be any benefit to such an approach, but if I can
        > figure out a means of quantifying the novelty, I'm gonna give it a whirl.
        > Gotta write up something interesting to graduate I suppose.
        >
        > Any thoughts would be greatly appreciated.
        >
        > -Drew
        >
        > On Sat, May 28, 2011 at 5:59 PM, Ken <kstanley@...> wrote:
        >
        > >
        > >
        > >
        > >
        > > Hi Drew, I just wanted to echo that I think combining novelty search with
        > > interaction between evolving agents is very interesting, if only we can find
        > > a way to characterize behavior generally enough to overcome the inherent
        > > noisiness of interaction. Of course, you have clearly been thinking about
        > > that, and it may be possible to make progress following your line of
        > > reasoning. Maybe if parasites could be categorized into classes and novelty
        > > was a concatenation of behaviors across all known classes it could make more
        > > sense of the behavior space than just a raw behavior characterization. I'm
        > > sure there are many other ways to think about it too.
        > >
        > > One other thing to note is that it may not really be "competitive"
        > > coevolution per se if you implemented such an experiment. If novelty is the
        > > driving force, it's not clearly competitive or cooperative, which of course
        > > is perfectly fine in any case.
        > >
        > > ken
        > >
        > >
        > > --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@>
        > > wrote:
        > > >
        > > > Joel,
        > > >
        > > > Thanks for the feedback. I was just thinking how difficult the problem
        > > would
        > > > be with the parasite agents doing things differently each time. Thus the
        > > > novelty metric would have to encompass the novel behavior relative to
        > > what
        > > > the parasite did.
        > > >
        > > > Another random thought is that if you could automate recognition of the
        > > > differing behaviors/techniques of the parasite, and develop a completely
        > > > different novelty search for just that one type parasitic behavior. Thus
        > > you
        > > > end up with a large modular NN, with each module being a novelty search
        > > > generated NN developed to handle that particular type of
        > > technique/behavior
        > > > of the parasite. A higher level NN would handle recognition of the
        > > > parasite's behavior, and select the appropriate NN module to use against
        > > the
        > > > parasite in that instance. I think I spotted some papers floating about
        > > on
        > > > automatic decomposition of problems, maybe that can feed into such random
        > > > thinking.
        > > >
        > > > Not a well formed thought as of yet, but it's always good to type out
        > > brain
        > > > farts.
        > > >
        > > >
        > > > -Drew
        > > >
        > > > On Fri, May 27, 2011 at 2:28 PM, joel278 <lehman.154@> wrote:
        > > >
        > > > >
        > > > >
        > > > > Hi Drew,
        > > > >
        > > > > As far as I know, competitive coevolution and novelty search have not
        > > yet
        > > > > been combined in any publications. Ken and I have had some discussions
        > > about
        > > > > possible ways to do it in the past, but haven't done any experiments.
        > > > >
        > > > > The main complication when combining both techniques is that the
        > > behavior
        > > > > of a particular individual is no longer statically well-defined in
        > > > > coevolution, but is dependent on what individual(s) it is evaluated
        > > with.
        > > > > For example, the board states that a checkers-playing agent proceeds
        > > through
        > > > > depends on its opponent.
        > > > >
        > > > > A similar issue would arise when applying novelty search in a noisy
        > > > > environment; its behavior might then be probabilistic. You could do
        > > multiple
        > > > > evaluations and have a behavioral characterization that is related to
        > > the
        > > > > distribution of behaviors. Alternatively, novelty search might be
        > > robust
        > > > > enough that nothing special needs to be done.
        > > > >
        > > > > This direction of research is very interesting though, and I hope that
        > > you
        > > > > follow up on it. I think it is particularly promising if done right
        > > because
        > > > > competitive coevolution is a potential a path to open-ended evolution
        > > (e.g.
        > > > > the red queen hypothesis). However, in practice coevolution is subject
        > > to
        > > > > coevolutionary forms of "deceptive local optima" (e.g. mediocre stable
        > > > > states, disengagement ,etc.) which novelty search has proved effective
        > > with
        > > > > dealing with in other non coevolutionary domains.
        > > > >
        > > > > Joel
        > > > >
        > > > >
        > > > > --- In neat@yahoogroups.com, "ze_dakster" <drew.kirkpatrick@> wrote:
        > > > > >
        > > > > > I'm curious about merging novelty search with competitive
        > > coevolution,
        > > > > and haven't been able to find any papers describing such an undertaking
        > > yet.
        > > > > Anyone aware of any papers covering that topic?
        > > > > >
        > > > > > Much thanks in advance for any tips.
        > > > > >
        > > > >
        > > > >
        > > > >
        > > >
        > >
        > >
        > >
        >
      • Drew Kirkpatrick
        Ken, Thanks for the tips. This is going to be my thesis for my second M.S. degree, in Computer Science this time. I think it will be interesting because it s
        Message 3 of 10 , Jun 9, 2011
          Ken,

          Thanks for the tips. 

          This is going to be my thesis for my second M.S. degree, in Computer Science this time. I think it will be interesting because it's rather different from my professional specialty of Human Factors. I'll go ahead and apologize in advance, over the next year I'm sure I'll be asking many questions in users group :)

          I'll let you know how it turns out.


          -Drew

          On Thu, Jun 9, 2011 at 5:53 PM, Ken <kstanley@...> wrote:
           



          Hi Drew, I understand the basic idea you have. It does sound like you have a workable idea for integrating novelty search into competitive coevolution. Of course, I'd be particularly careful on the way behavior is measured because it is the key to identifying novelty. One tip is to make sure you don't only include raw outputs or raw inputs as part of the behavior characterization, because what matters most is what an agent actually does, as opposed to what it wants to do. For example, if an agent spend 100 timesteps trying to run through a wall, we would want to characterize its behavior as being stalled rather than as moving forward.

          Also, one of the big challenges in competitive coevolution (and alife in general) is to create a domain that is open-ended enough to support something interesting arising. The robot duel was my attempt to do that, but perhaps it could be enhanced to support more open-endedness, though I don't know how off-hand. But the risk you always have in these domains is that even if you have a fantastic algorithmic setup that in principle could discover amazing behaviors, it is always possible that the domain itself only supports a limited range of strategies. For example, it is hard to imagine strategies in the robot duel that go very far beyond the one shown here:

          http://www.cs.utexas.edu/users/nn/pages/research/robotmovies/clip8.gif

          In any case, overall I think your idea can make a good experiment. You mention that you need to write something up for graduation - what degree are you working on?



          ken

          --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@...> wrote:
          >
          > Ken,
          >
          > I think I get what you're saying about categorizing parasites (or, their
          > behavior) into classes. I'm thinking in particular about the robot duel from
          > your paper "Competitive Coevolution through Evolutionary Complexiï¬ cation".

          > Instead of categorizing the parasite behavior, I was thinking break out
          > meaningful classifications of sensor inputs. Classification of behavior of
          > the host would based on it's movement vector and speed (moving away,
          > towards, fast/slow, going after food, etc). Of course, this is a dynamic
          > environment.
          >
          > So for each time the classification of inputs changes, the behavior of the
          > host is classified and checked for novelty. These individual novelty
          > measurements are all added up at the end of the run, and divided by the
          > number of class of input changes to normalize things.
          >
          > Still spit-balling here.
          >
          > As far as making it real "competitive coevolution", of course a record of
          > who won is essentially a fitness measure, so there'd have to be a hybrid
          > novelty/fitness in there somewhere, because measuring who won is not a
          > novelty measure.
          >
          > I still think novelty search brings a lot of benefits to the table. My
          > current spit-ball is that there is an added parameter for population growth
          > allowance for the host group. Instead of a fitness function, a novelty
          > metric is used (assuming one can be made, obviously that's tricky). The host
          > population remains the hosts until their population has grown the specified
          > amount. I'm hoping that will encourage a nice broad range of strategies to
          > be evaluated. Once that max population % has been hit, a "cataclysmic event"
          > occurs (cataclysm-neat? rapture-neat? Harold Camping-neat?) to wipe out the
          > extra population, and only the best performing hosts are kept, which would
          > be how it integrates into the competition side of things. .
          >
          > Then the parasites and hosts flip. Essentially novelty is used to explore
          > differing behaviors up until the cataclysmic event, then performance is used
          > to prune the population back down, and give the "other team" their go.
          >
          > Not sure if there would be any benefit to such an approach, but if I can
          > figure out a means of quantifying the novelty, I'm gonna give it a whirl.
          > Gotta write up something interesting to graduate I suppose.
          >
          > Any thoughts would be greatly appreciated.
          >
          > -Drew
          >
          > On Sat, May 28, 2011 at 5:59 PM, Ken <kstanley@...> wrote:
          >
          > >
          > >
          > >
          > >
          > > Hi Drew, I just wanted to echo that I think combining novelty search with
          > > interaction between evolving agents is very interesting, if only we can find
          > > a way to characterize behavior generally enough to overcome the inherent
          > > noisiness of interaction. Of course, you have clearly been thinking about
          > > that, and it may be possible to make progress following your line of
          > > reasoning. Maybe if parasites could be categorized into classes and novelty
          > > was a concatenation of behaviors across all known classes it could make more
          > > sense of the behavior space than just a raw behavior characterization. I'm
          > > sure there are many other ways to think about it too.
          > >
          > > One other thing to note is that it may not really be "competitive"
          > > coevolution per se if you implemented such an experiment. If novelty is the
          > > driving force, it's not clearly competitive or cooperative, which of course
          > > is perfectly fine in any case.
          > >
          > > ken
          > >
          > >
          > > --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@>
          > > wrote:
          > > >
          > > > Joel,
          > > >
          > > > Thanks for the feedback. I was just thinking how difficult the problem
          > > would
          > > > be with the parasite agents doing things differently each time. Thus the
          > > > novelty metric would have to encompass the novel behavior relative to
          > > what
          > > > the parasite did.
          > > >
          > > > Another random thought is that if you could automate recognition of the
          > > > differing behaviors/techniques of the parasite, and develop a completely
          > > > different novelty search for just that one type parasitic behavior. Thus
          > > you
          > > > end up with a large modular NN, with each module being a novelty search
          > > > generated NN developed to handle that particular type of
          > > technique/behavior
          > > > of the parasite. A higher level NN would handle recognition of the
          > > > parasite's behavior, and select the appropriate NN module to use against
          > > the
          > > > parasite in that instance. I think I spotted some papers floating about
          > > on
          > > > automatic decomposition of problems, maybe that can feed into such random
          > > > thinking.
          > > >
          > > > Not a well formed thought as of yet, but it's always good to type out
          > > brain
          > > > farts.
          > > >
          > > >
          > > > -Drew
          > > >
          > > > On Fri, May 27, 2011 at 2:28 PM, joel278 <lehman.154@> wrote:
          > > >
          > > > >
          > > > >
          > > > > Hi Drew,
          > > > >
          > > > > As far as I know, competitive coevolution and novelty search have not
          > > yet
          > > > > been combined in any publications. Ken and I have had some discussions
          > > about
          > > > > possible ways to do it in the past, but haven't done any experiments.
          > > > >
          > > > > The main complication when combining both techniques is that the
          > > behavior
          > > > > of a particular individual is no longer statically well-defined in
          > > > > coevolution, but is dependent on what individual(s) it is evaluated
          > > with.
          > > > > For example, the board states that a checkers-playing agent proceeds
          > > through
          > > > > depends on its opponent.
          > > > >
          > > > > A similar issue would arise when applying novelty search in a noisy
          > > > > environment; its behavior might then be probabilistic. You could do
          > > multiple
          > > > > evaluations and have a behavioral characterization that is related to
          > > the
          > > > > distribution of behaviors. Alternatively, novelty search might be
          > > robust
          > > > > enough that nothing special needs to be done.
          > > > >
          > > > > This direction of research is very interesting though, and I hope that
          > > you
          > > > > follow up on it. I think it is particularly promising if done right
          > > because
          > > > > competitive coevolution is a potential a path to open-ended evolution
          > > (e.g.
          > > > > the red queen hypothesis). However, in practice coevolution is subject
          > > to
          > > > > coevolutionary forms of "deceptive local optima" (e.g. mediocre stable
          > > > > states, disengagement ,etc.) which novelty search has proved effective
          > > with
          > > > > dealing with in other non coevolutionary domains.
          > > > >
          > > > > Joel
          > > > >
          > > > >
          > > > > --- In neat@yahoogroups.com, "ze_dakster" <drew.kirkpatrick@> wrote:
          > > > > >
          > > > > > I'm curious about merging novelty search with competitive
          > > coevolution,
          > > > > and haven't been able to find any papers describing such an undertaking
          > > yet.
          > > > > Anyone aware of any papers covering that topic?
          > > > > >
          > > > > > Much thanks in advance for any tips.
          > > > > >
          > > > >
          > > > >
          > > > >
          > > >
          > >
          > >
          > >
          >


        • stephane.doncieux
          Hi Ken, just a point concerning behavior characterization. You can actually use raw inputs and raw outputs. Your robot will probably have sensors to detect
          Message 4 of 10 , Jun 10, 2011
            Hi Ken,

            just a point concerning behavior characterization. You can actually use raw inputs and raw outputs. Your robot will probably have sensors to detect collision with a wall -- a bumper for instance -- at least if you want it to react to such a situation. "Stalled against a wall" can then easily be detected relative to "going forward" because of the value of such a sensor and then considered as different.

            We have add very good results with novelty search or behavioral diversity while using a discretized version of the stream of inputs and outputs (simply 0 if below min+range/2 and 1 otherwise) and the hamming distance to compute behavioral distances. See for instance:

            * Doncieux, S. and Mouret, J.-B. (2010). Behavioral diversity measures for Evolutionary Robotics. IEEE Congress on Evolutionary Computation, 2010 (CEC 2010).
            http://pages.isir.upmc.fr/evorob_db/moin.wsgi/BehavioraldiversitymeasuresforEvolutionaryRobotics
            * T. Pinville, S. Koos, J.-B. Mouret , S. Doncieux (2011). How to Promote Generalisation in Evolutionary Robotics: the ProGAb Approach. GECCO 2011
            http://pages.isir.upmc.fr/evorob_db/moin.wsgi/HowToPromoteGeneralisationInErProGAb

            It is quite surprising how efficient it can be, but results are here. A paper of us should appear soon in Evolutionary Computation in which we performed intensive comparisons.

            It is anyway not clear yet whether it scales well or not with a bigger set inputs/outputs, but we have noticed good results with this behavior characterization on problems with up to 16 sensors+effectors.

            stephane

            --- In neat@yahoogroups.com, "Ken" <kstanley@...> wrote:
            >
            >
            >
            > Hi Drew, I understand the basic idea you have. It does sound like you have a workable idea for integrating novelty search into competitive coevolution. Of course, I'd be particularly careful on the way behavior is measured because it is the key to identifying novelty. One tip is to make sure you don't only include raw outputs or raw inputs as part of the behavior characterization, because what matters most is what an agent actually does, as opposed to what it wants to do. For example, if an agent spend 100 timesteps trying to run through a wall, we would want to characterize its behavior as being stalled rather than as moving forward.
            >
            > Also, one of the big challenges in competitive coevolution (and alife in general) is to create a domain that is open-ended enough to support something interesting arising. The robot duel was my attempt to do that, but perhaps it could be enhanced to support more open-endedness, though I don't know how off-hand. But the risk you always have in these domains is that even if you have a fantastic algorithmic setup that in principle could discover amazing behaviors, it is always possible that the domain itself only supports a limited range of strategies. For example, it is hard to imagine strategies in the robot duel that go very far beyond the one shown here:
            >
            > http://www.cs.utexas.edu/users/nn/pages/research/robotmovies/clip8.gif
            >
            > In any case, overall I think your idea can make a good experiment. You mention that you need to write something up for graduation - what degree are you working on?
            >
            > ken
            >
            > --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@> wrote:
            > >
            > > Ken,
            > >
            > > I think I get what you're saying about categorizing parasites (or, their
            > > behavior) into classes. I'm thinking in particular about the robot duel from
            > > your paper "Competitive Coevolution through Evolutionary Complexification".
            > > Instead of categorizing the parasite behavior, I was thinking break out
            > > meaningful classifications of sensor inputs. Classification of behavior of
            > > the host would based on it's movement vector and speed (moving away,
            > > towards, fast/slow, going after food, etc). Of course, this is a dynamic
            > > environment.
            > >
            > > So for each time the classification of inputs changes, the behavior of the
            > > host is classified and checked for novelty. These individual novelty
            > > measurements are all added up at the end of the run, and divided by the
            > > number of class of input changes to normalize things.
            > >
            > > Still spit-balling here.
            > >
            > > As far as making it real "competitive coevolution", of course a record of
            > > who won is essentially a fitness measure, so there'd have to be a hybrid
            > > novelty/fitness in there somewhere, because measuring who won is not a
            > > novelty measure.
            > >
            > > I still think novelty search brings a lot of benefits to the table. My
            > > current spit-ball is that there is an added parameter for population growth
            > > allowance for the host group. Instead of a fitness function, a novelty
            > > metric is used (assuming one can be made, obviously that's tricky). The host
            > > population remains the hosts until their population has grown the specified
            > > amount. I'm hoping that will encourage a nice broad range of strategies to
            > > be evaluated. Once that max population % has been hit, a "cataclysmic event"
            > > occurs (cataclysm-neat? rapture-neat? Harold Camping-neat?) to wipe out the
            > > extra population, and only the best performing hosts are kept, which would
            > > be how it integrates into the competition side of things. .
            > >
            > > Then the parasites and hosts flip. Essentially novelty is used to explore
            > > differing behaviors up until the cataclysmic event, then performance is used
            > > to prune the population back down, and give the "other team" their go.
            > >
            > > Not sure if there would be any benefit to such an approach, but if I can
            > > figure out a means of quantifying the novelty, I'm gonna give it a whirl.
            > > Gotta write up something interesting to graduate I suppose.
            > >
            > > Any thoughts would be greatly appreciated.
            > >
            > > -Drew
            > >
            > > On Sat, May 28, 2011 at 5:59 PM, Ken <kstanley@> wrote:
            > >
            > > >
            > > >
            > > >
            > > >
            > > > Hi Drew, I just wanted to echo that I think combining novelty search with
            > > > interaction between evolving agents is very interesting, if only we can find
            > > > a way to characterize behavior generally enough to overcome the inherent
            > > > noisiness of interaction. Of course, you have clearly been thinking about
            > > > that, and it may be possible to make progress following your line of
            > > > reasoning. Maybe if parasites could be categorized into classes and novelty
            > > > was a concatenation of behaviors across all known classes it could make more
            > > > sense of the behavior space than just a raw behavior characterization. I'm
            > > > sure there are many other ways to think about it too.
            > > >
            > > > One other thing to note is that it may not really be "competitive"
            > > > coevolution per se if you implemented such an experiment. If novelty is the
            > > > driving force, it's not clearly competitive or cooperative, which of course
            > > > is perfectly fine in any case.
            > > >
            > > > ken
            > > >
            > > >
            > > > --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@>
            > > > wrote:
            > > > >
            > > > > Joel,
            > > > >
            > > > > Thanks for the feedback. I was just thinking how difficult the problem
            > > > would
            > > > > be with the parasite agents doing things differently each time. Thus the
            > > > > novelty metric would have to encompass the novel behavior relative to
            > > > what
            > > > > the parasite did.
            > > > >
            > > > > Another random thought is that if you could automate recognition of the
            > > > > differing behaviors/techniques of the parasite, and develop a completely
            > > > > different novelty search for just that one type parasitic behavior. Thus
            > > > you
            > > > > end up with a large modular NN, with each module being a novelty search
            > > > > generated NN developed to handle that particular type of
            > > > technique/behavior
            > > > > of the parasite. A higher level NN would handle recognition of the
            > > > > parasite's behavior, and select the appropriate NN module to use against
            > > > the
            > > > > parasite in that instance. I think I spotted some papers floating about
            > > > on
            > > > > automatic decomposition of problems, maybe that can feed into such random
            > > > > thinking.
            > > > >
            > > > > Not a well formed thought as of yet, but it's always good to type out
            > > > brain
            > > > > farts.
            > > > >
            > > > >
            > > > > -Drew
            > > > >
            > > > > On Fri, May 27, 2011 at 2:28 PM, joel278 <lehman.154@> wrote:
            > > > >
            > > > > >
            > > > > >
            > > > > > Hi Drew,
            > > > > >
            > > > > > As far as I know, competitive coevolution and novelty search have not
            > > > yet
            > > > > > been combined in any publications. Ken and I have had some discussions
            > > > about
            > > > > > possible ways to do it in the past, but haven't done any experiments.
            > > > > >
            > > > > > The main complication when combining both techniques is that the
            > > > behavior
            > > > > > of a particular individual is no longer statically well-defined in
            > > > > > coevolution, but is dependent on what individual(s) it is evaluated
            > > > with.
            > > > > > For example, the board states that a checkers-playing agent proceeds
            > > > through
            > > > > > depends on its opponent.
            > > > > >
            > > > > > A similar issue would arise when applying novelty search in a noisy
            > > > > > environment; its behavior might then be probabilistic. You could do
            > > > multiple
            > > > > > evaluations and have a behavioral characterization that is related to
            > > > the
            > > > > > distribution of behaviors. Alternatively, novelty search might be
            > > > robust
            > > > > > enough that nothing special needs to be done.
            > > > > >
            > > > > > This direction of research is very interesting though, and I hope that
            > > > you
            > > > > > follow up on it. I think it is particularly promising if done right
            > > > because
            > > > > > competitive coevolution is a potential a path to open-ended evolution
            > > > (e.g.
            > > > > > the red queen hypothesis). However, in practice coevolution is subject
            > > > to
            > > > > > coevolutionary forms of "deceptive local optima" (e.g. mediocre stable
            > > > > > states, disengagement ,etc.) which novelty search has proved effective
            > > > with
            > > > > > dealing with in other non coevolutionary domains.
            > > > > >
            > > > > > Joel
            > > > > >
            > > > > >
            > > > > > --- In neat@yahoogroups.com, "ze_dakster" <drew.kirkpatrick@> wrote:
            > > > > > >
            > > > > > > I'm curious about merging novelty search with competitive
            > > > coevolution,
            > > > > > and haven't been able to find any papers describing such an undertaking
            > > > yet.
            > > > > > Anyone aware of any papers covering that topic?
            > > > > > >
            > > > > > > Much thanks in advance for any tips.
            > > > > > >
            > > > > >
            > > > > >
            > > > > >
            > > > >
            > > >
            > > >
            > > >
            > >
            >
          • Drew Kirkpatrick
            Stephane, Thanks for passing along your papers, they were very interesting reads and such an approach could work well for my particular need. I m curious as to
            Message 5 of 10 , Jun 11, 2011
              Stephane,

              Thanks for passing along your papers, they were very interesting reads and such an approach could work well for my particular need. 

              I'm curious as to why you chose to use hamming distance as opposed to normalized compression distance? I would imagine that if you have strings of equal length for comparison, then hamming distance would be considerably faster, but you can only use it in cases where the strings are of equal length, correct?

              -Drew

              On Fri, Jun 10, 2011 at 4:29 AM, stephane.doncieux <stephane.doncieux@...> wrote:
               

              Hi Ken,

              just a point concerning behavior characterization. You can actually use raw inputs and raw outputs. Your robot will probably have sensors to detect collision with a wall -- a bumper for instance -- at least if you want it to react to such a situation. "Stalled against a wall" can then easily be detected relative to "going forward" because of the value of such a sensor and then considered as different.

              We have add very good results with novelty search or behavioral diversity while using a discretized version of the stream of inputs and outputs (simply 0 if below min+range/2 and 1 otherwise) and the hamming distance to compute behavioral distances. See for instance:

              * Doncieux, S. and Mouret, J.-B. (2010). Behavioral diversity measures for Evolutionary Robotics. IEEE Congress on Evolutionary Computation, 2010 (CEC 2010).
              http://pages.isir.upmc.fr/evorob_db/moin.wsgi/BehavioraldiversitymeasuresforEvolutionaryRobotics
              * T. Pinville, S. Koos, J.-B. Mouret , S. Doncieux (2011). How to Promote Generalisation in Evolutionary Robotics: the ProGAb Approach. GECCO 2011
              http://pages.isir.upmc.fr/evorob_db/moin.wsgi/HowToPromoteGeneralisationInErProGAb

              It is quite surprising how efficient it can be, but results are here. A paper of us should appear soon in Evolutionary Computation in which we performed intensive comparisons.

              It is anyway not clear yet whether it scales well or not with a bigger set inputs/outputs, but we have noticed good results with this behavior characterization on problems with up to 16 sensors+effectors.

              stephane



              --- In neat@yahoogroups.com, "Ken" <kstanley@...> wrote:
              >
              >
              >
              > Hi Drew, I understand the basic idea you have. It does sound like you have a workable idea for integrating novelty search into competitive coevolution. Of course, I'd be particularly careful on the way behavior is measured because it is the key to identifying novelty. One tip is to make sure you don't only include raw outputs or raw inputs as part of the behavior characterization, because what matters most is what an agent actually does, as opposed to what it wants to do. For example, if an agent spend 100 timesteps trying to run through a wall, we would want to characterize its behavior as being stalled rather than as moving forward.
              >
              > Also, one of the big challenges in competitive coevolution (and alife in general) is to create a domain that is open-ended enough to support something interesting arising. The robot duel was my attempt to do that, but perhaps it could be enhanced to support more open-endedness, though I don't know how off-hand. But the risk you always have in these domains is that even if you have a fantastic algorithmic setup that in principle could discover amazing behaviors, it is always possible that the domain itself only supports a limited range of strategies. For example, it is hard to imagine strategies in the robot duel that go very far beyond the one shown here:
              >
              > http://www.cs.utexas.edu/users/nn/pages/research/robotmovies/clip8.gif
              >
              > In any case, overall I think your idea can make a good experiment. You mention that you need to write something up for graduation - what degree are you working on?
              >
              > ken
              >
              > --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@> wrote:
              > >
              > > Ken,
              > >
              > > I think I get what you're saying about categorizing parasites (or, their
              > > behavior) into classes. I'm thinking in particular about the robot duel from
              > > your paper "Competitive Coevolution through Evolutionary Complexiï¬ cation".
              > > Instead of categorizing the parasite behavior, I was thinking break out
              > > meaningful classifications of sensor inputs. Classification of behavior of
              > > the host would based on it's movement vector and speed (moving away,
              > > towards, fast/slow, going after food, etc). Of course, this is a dynamic
              > > environment.
              > >
              > > So for each time the classification of inputs changes, the behavior of the
              > > host is classified and checked for novelty. These individual novelty
              > > measurements are all added up at the end of the run, and divided by the
              > > number of class of input changes to normalize things.
              > >
              > > Still spit-balling here.
              > >
              > > As far as making it real "competitive coevolution", of course a record of
              > > who won is essentially a fitness measure, so there'd have to be a hybrid
              > > novelty/fitness in there somewhere, because measuring who won is not a
              > > novelty measure.
              > >
              > > I still think novelty search brings a lot of benefits to the table. My
              > > current spit-ball is that there is an added parameter for population growth
              > > allowance for the host group. Instead of a fitness function, a novelty
              > > metric is used (assuming one can be made, obviously that's tricky). The host
              > > population remains the hosts until their population has grown the specified
              > > amount. I'm hoping that will encourage a nice broad range of strategies to
              > > be evaluated. Once that max population % has been hit, a "cataclysmic event"
              > > occurs (cataclysm-neat? rapture-neat? Harold Camping-neat?) to wipe out the
              > > extra population, and only the best performing hosts are kept, which would
              > > be how it integrates into the competition side of things. .
              > >
              > > Then the parasites and hosts flip. Essentially novelty is used to explore
              > > differing behaviors up until the cataclysmic event, then performance is used
              > > to prune the population back down, and give the "other team" their go.
              > >
              > > Not sure if there would be any benefit to such an approach, but if I can
              > > figure out a means of quantifying the novelty, I'm gonna give it a whirl.
              > > Gotta write up something interesting to graduate I suppose.
              > >
              > > Any thoughts would be greatly appreciated.
              > >
              > > -Drew
              > >
              > > On Sat, May 28, 2011 at 5:59 PM, Ken <kstanley@> wrote:
              > >
              > > >
              > > >
              > > >
              > > >
              > > > Hi Drew, I just wanted to echo that I think combining novelty search with
              > > > interaction between evolving agents is very interesting, if only we can find
              > > > a way to characterize behavior generally enough to overcome the inherent
              > > > noisiness of interaction. Of course, you have clearly been thinking about
              > > > that, and it may be possible to make progress following your line of
              > > > reasoning. Maybe if parasites could be categorized into classes and novelty
              > > > was a concatenation of behaviors across all known classes it could make more
              > > > sense of the behavior space than just a raw behavior characterization. I'm
              > > > sure there are many other ways to think about it too.
              > > >
              > > > One other thing to note is that it may not really be "competitive"
              > > > coevolution per se if you implemented such an experiment. If novelty is the
              > > > driving force, it's not clearly competitive or cooperative, which of course
              > > > is perfectly fine in any case.
              > > >
              > > > ken
              > > >
              > > >
              > > > --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@>
              > > > wrote:
              > > > >
              > > > > Joel,
              > > > >
              > > > > Thanks for the feedback. I was just thinking how difficult the problem
              > > > would
              > > > > be with the parasite agents doing things differently each time. Thus the
              > > > > novelty metric would have to encompass the novel behavior relative to
              > > > what
              > > > > the parasite did.
              > > > >
              > > > > Another random thought is that if you could automate recognition of the
              > > > > differing behaviors/techniques of the parasite, and develop a completely
              > > > > different novelty search for just that one type parasitic behavior. Thus
              > > > you
              > > > > end up with a large modular NN, with each module being a novelty search
              > > > > generated NN developed to handle that particular type of
              > > > technique/behavior
              > > > > of the parasite. A higher level NN would handle recognition of the
              > > > > parasite's behavior, and select the appropriate NN module to use against
              > > > the
              > > > > parasite in that instance. I think I spotted some papers floating about
              > > > on
              > > > > automatic decomposition of problems, maybe that can feed into such random
              > > > > thinking.
              > > > >
              > > > > Not a well formed thought as of yet, but it's always good to type out
              > > > brain
              > > > > farts.
              > > > >
              > > > >
              > > > > -Drew
              > > > >
              > > > > On Fri, May 27, 2011 at 2:28 PM, joel278 <lehman.154@> wrote:
              > > > >
              > > > > >
              > > > > >
              > > > > > Hi Drew,
              > > > > >
              > > > > > As far as I know, competitive coevolution and novelty search have not
              > > > yet
              > > > > > been combined in any publications. Ken and I have had some discussions
              > > > about
              > > > > > possible ways to do it in the past, but haven't done any experiments.
              > > > > >
              > > > > > The main complication when combining both techniques is that the
              > > > behavior
              > > > > > of a particular individual is no longer statically well-defined in
              > > > > > coevolution, but is dependent on what individual(s) it is evaluated
              > > > with.
              > > > > > For example, the board states that a checkers-playing agent proceeds
              > > > through
              > > > > > depends on its opponent.
              > > > > >
              > > > > > A similar issue would arise when applying novelty search in a noisy
              > > > > > environment; its behavior might then be probabilistic. You could do
              > > > multiple
              > > > > > evaluations and have a behavioral characterization that is related to
              > > > the
              > > > > > distribution of behaviors. Alternatively, novelty search might be
              > > > robust
              > > > > > enough that nothing special needs to be done.
              > > > > >
              > > > > > This direction of research is very interesting though, and I hope that
              > > > you
              > > > > > follow up on it. I think it is particularly promising if done right
              > > > because
              > > > > > competitive coevolution is a potential a path to open-ended evolution
              > > > (e.g.
              > > > > > the red queen hypothesis). However, in practice coevolution is subject
              > > > to
              > > > > > coevolutionary forms of "deceptive local optima" (e.g. mediocre stable
              > > > > > states, disengagement ,etc.) which novelty search has proved effective
              > > > with
              > > > > > dealing with in other non coevolutionary domains.
              > > > > >
              > > > > > Joel
              > > > > >
              > > > > >
              > > > > > --- In neat@yahoogroups.com, "ze_dakster" <drew.kirkpatrick@> wrote:
              > > > > > >
              > > > > > > I'm curious about merging novelty search with competitive
              > > > coevolution,
              > > > > > and haven't been able to find any papers describing such an undertaking
              > > > yet.
              > > > > > Anyone aware of any papers covering that topic?
              > > > > > >
              > > > > > > Much thanks in advance for any tips.
              > > > > > >
              > > > > >
              > > > > >
              > > > > >
              > > > >
              > > >
              > > >
              > > >
              > >
              >


            • Drew Kirkpatrick
              Stephane, Nevermind about my question, I just noticed in the paper where you said that NCD was too slow for your application. Very useful technique regardless.
              Message 6 of 10 , Jun 12, 2011
                Stephane,

                Nevermind about my question, I just noticed in the paper where you said that NCD was too slow for your application. Very useful technique regardless. 


                -Drew

                On Sat, Jun 11, 2011 at 4:57 PM, Drew Kirkpatrick <drew.kirkpatrick@...> wrote:
                Stephane,

                Thanks for passing along your papers, they were very interesting reads and such an approach could work well for my particular need. 

                I'm curious as to why you chose to use hamming distance as opposed to normalized compression distance? I would imagine that if you have strings of equal length for comparison, then hamming distance would be considerably faster, but you can only use it in cases where the strings are of equal length, correct?

                -Drew


                On Fri, Jun 10, 2011 at 4:29 AM, stephane.doncieux <stephane.doncieux@...> wrote:
                 

                Hi Ken,

                just a point concerning behavior characterization. You can actually use raw inputs and raw outputs. Your robot will probably have sensors to detect collision with a wall -- a bumper for instance -- at least if you want it to react to such a situation. "Stalled against a wall" can then easily be detected relative to "going forward" because of the value of such a sensor and then considered as different.

                We have add very good results with novelty search or behavioral diversity while using a discretized version of the stream of inputs and outputs (simply 0 if below min+range/2 and 1 otherwise) and the hamming distance to compute behavioral distances. See for instance:

                * Doncieux, S. and Mouret, J.-B. (2010). Behavioral diversity measures for Evolutionary Robotics. IEEE Congress on Evolutionary Computation, 2010 (CEC 2010).
                http://pages.isir.upmc.fr/evorob_db/moin.wsgi/BehavioraldiversitymeasuresforEvolutionaryRobotics
                * T. Pinville, S. Koos, J.-B. Mouret , S. Doncieux (2011). How to Promote Generalisation in Evolutionary Robotics: the ProGAb Approach. GECCO 2011
                http://pages.isir.upmc.fr/evorob_db/moin.wsgi/HowToPromoteGeneralisationInErProGAb

                It is quite surprising how efficient it can be, but results are here. A paper of us should appear soon in Evolutionary Computation in which we performed intensive comparisons.

                It is anyway not clear yet whether it scales well or not with a bigger set inputs/outputs, but we have noticed good results with this behavior characterization on problems with up to 16 sensors+effectors.

                stephane



                --- In neat@yahoogroups.com, "Ken" <kstanley@...> wrote:
                >
                >
                >
                > Hi Drew, I understand the basic idea you have. It does sound like you have a workable idea for integrating novelty search into competitive coevolution. Of course, I'd be particularly careful on the way behavior is measured because it is the key to identifying novelty. One tip is to make sure you don't only include raw outputs or raw inputs as part of the behavior characterization, because what matters most is what an agent actually does, as opposed to what it wants to do. For example, if an agent spend 100 timesteps trying to run through a wall, we would want to characterize its behavior as being stalled rather than as moving forward.
                >
                > Also, one of the big challenges in competitive coevolution (and alife in general) is to create a domain that is open-ended enough to support something interesting arising. The robot duel was my attempt to do that, but perhaps it could be enhanced to support more open-endedness, though I don't know how off-hand. But the risk you always have in these domains is that even if you have a fantastic algorithmic setup that in principle could discover amazing behaviors, it is always possible that the domain itself only supports a limited range of strategies. For example, it is hard to imagine strategies in the robot duel that go very far beyond the one shown here:
                >
                > http://www.cs.utexas.edu/users/nn/pages/research/robotmovies/clip8.gif
                >
                > In any case, overall I think your idea can make a good experiment. You mention that you need to write something up for graduation - what degree are you working on?
                >
                > ken
                >
                > --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@> wrote:
                > >
                > > Ken,
                > >
                > > I think I get what you're saying about categorizing parasites (or, their
                > > behavior) into classes. I'm thinking in particular about the robot duel from
                > > your paper "Competitive Coevolution through Evolutionary Complexiï¬ cation".
                > > Instead of categorizing the parasite behavior, I was thinking break out
                > > meaningful classifications of sensor inputs. Classification of behavior of
                > > the host would based on it's movement vector and speed (moving away,
                > > towards, fast/slow, going after food, etc). Of course, this is a dynamic
                > > environment.
                > >
                > > So for each time the classification of inputs changes, the behavior of the
                > > host is classified and checked for novelty. These individual novelty
                > > measurements are all added up at the end of the run, and divided by the
                > > number of class of input changes to normalize things.
                > >
                > > Still spit-balling here.
                > >
                > > As far as making it real "competitive coevolution", of course a record of
                > > who won is essentially a fitness measure, so there'd have to be a hybrid
                > > novelty/fitness in there somewhere, because measuring who won is not a
                > > novelty measure.
                > >
                > > I still think novelty search brings a lot of benefits to the table. My
                > > current spit-ball is that there is an added parameter for population growth
                > > allowance for the host group. Instead of a fitness function, a novelty
                > > metric is used (assuming one can be made, obviously that's tricky). The host
                > > population remains the hosts until their population has grown the specified
                > > amount. I'm hoping that will encourage a nice broad range of strategies to
                > > be evaluated. Once that max population % has been hit, a "cataclysmic event"
                > > occurs (cataclysm-neat? rapture-neat? Harold Camping-neat?) to wipe out the
                > > extra population, and only the best performing hosts are kept, which would
                > > be how it integrates into the competition side of things. .
                > >
                > > Then the parasites and hosts flip. Essentially novelty is used to explore
                > > differing behaviors up until the cataclysmic event, then performance is used
                > > to prune the population back down, and give the "other team" their go.
                > >
                > > Not sure if there would be any benefit to such an approach, but if I can
                > > figure out a means of quantifying the novelty, I'm gonna give it a whirl.
                > > Gotta write up something interesting to graduate I suppose.
                > >
                > > Any thoughts would be greatly appreciated.
                > >
                > > -Drew
                > >
                > > On Sat, May 28, 2011 at 5:59 PM, Ken <kstanley@> wrote:
                > >
                > > >
                > > >
                > > >
                > > >
                > > > Hi Drew, I just wanted to echo that I think combining novelty search with
                > > > interaction between evolving agents is very interesting, if only we can find
                > > > a way to characterize behavior generally enough to overcome the inherent
                > > > noisiness of interaction. Of course, you have clearly been thinking about
                > > > that, and it may be possible to make progress following your line of
                > > > reasoning. Maybe if parasites could be categorized into classes and novelty
                > > > was a concatenation of behaviors across all known classes it could make more
                > > > sense of the behavior space than just a raw behavior characterization. I'm
                > > > sure there are many other ways to think about it too.
                > > >
                > > > One other thing to note is that it may not really be "competitive"
                > > > coevolution per se if you implemented such an experiment. If novelty is the
                > > > driving force, it's not clearly competitive or cooperative, which of course
                > > > is perfectly fine in any case.
                > > >
                > > > ken
                > > >
                > > >
                > > > --- In neat@yahoogroups.com, Drew Kirkpatrick <drew.kirkpatrick@>
                > > > wrote:
                > > > >
                > > > > Joel,
                > > > >
                > > > > Thanks for the feedback. I was just thinking how difficult the problem
                > > > would
                > > > > be with the parasite agents doing things differently each time. Thus the
                > > > > novelty metric would have to encompass the novel behavior relative to
                > > > what
                > > > > the parasite did.
                > > > >
                > > > > Another random thought is that if you could automate recognition of the
                > > > > differing behaviors/techniques of the parasite, and develop a completely
                > > > > different novelty search for just that one type parasitic behavior. Thus
                > > > you
                > > > > end up with a large modular NN, with each module being a novelty search
                > > > > generated NN developed to handle that particular type of
                > > > technique/behavior
                > > > > of the parasite. A higher level NN would handle recognition of the
                > > > > parasite's behavior, and select the appropriate NN module to use against
                > > > the
                > > > > parasite in that instance. I think I spotted some papers floating about
                > > > on
                > > > > automatic decomposition of problems, maybe that can feed into such random
                > > > > thinking.
                > > > >
                > > > > Not a well formed thought as of yet, but it's always good to type out
                > > > brain
                > > > > farts.
                > > > >
                > > > >
                > > > > -Drew
                > > > >
                > > > > On Fri, May 27, 2011 at 2:28 PM, joel278 <lehman.154@> wrote:
                > > > >
                > > > > >
                > > > > >
                > > > > > Hi Drew,
                > > > > >
                > > > > > As far as I know, competitive coevolution and novelty search have not
                > > > yet
                > > > > > been combined in any publications. Ken and I have had some discussions
                > > > about
                > > > > > possible ways to do it in the past, but haven't done any experiments.
                > > > > >
                > > > > > The main complication when combining both techniques is that the
                > > > behavior
                > > > > > of a particular individual is no longer statically well-defined in
                > > > > > coevolution, but is dependent on what individual(s) it is evaluated
                > > > with.
                > > > > > For example, the board states that a checkers-playing agent proceeds
                > > > through
                > > > > > depends on its opponent.
                > > > > >
                > > > > > A similar issue would arise when applying novelty search in a noisy
                > > > > > environment; its behavior might then be probabilistic. You could do
                > > > multiple
                > > > > > evaluations and have a behavioral characterization that is related to
                > > > the
                > > > > > distribution of behaviors. Alternatively, novelty search might be
                > > > robust
                > > > > > enough that nothing special needs to be done.
                > > > > >
                > > > > > This direction of research is very interesting though, and I hope that
                > > > you
                > > > > > follow up on it. I think it is particularly promising if done right
                > > > because
                > > > > > competitive coevolution is a potential a path to open-ended evolution
                > > > (e.g.
                > > > > > the red queen hypothesis). However, in practice coevolution is subject
                > > > to
                > > > > > coevolutionary forms of "deceptive local optima" (e.g. mediocre stable
                > > > > > states, disengagement ,etc.) which novelty search has proved effective
                > > > with
                > > > > > dealing with in other non coevolutionary domains.
                > > > > >
                > > > > > Joel
                > > > > >
                > > > > >
                > > > > > --- In neat@yahoogroups.com, "ze_dakster" <drew.kirkpatrick@> wrote:
                > > > > > >
                > > > > > > I'm curious about merging novelty search with competitive
                > > > coevolution,
                > > > > > and haven't been able to find any papers describing such an undertaking
                > > > yet.
                > > > > > Anyone aware of any papers covering that topic?
                > > > > > >
                > > > > > > Much thanks in advance for any tips.
                > > > > > >
                > > > > >
                > > > > >
                > > > > >
                > > > >
                > > >
                > > >
                > > >
                > >
                >



              Your message has been successfully submitted and would be delivered to recipients shortly.