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

Re: [neat] Re: Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding

Expand Messages
  • Vinod K. Valsalam
    Ken, I tested networks that output desired angles instead of angular velocities using the same modular setup described in my GECCO paper. The hip joints of the
    Message 1 of 42 , Mar 2, 2009
      Ken,

      I tested networks that output desired angles instead of angular
      velocities using the same modular setup described in my GECCO paper.
      The hip joints of the quadruped robot are universal joints, having two
      angles (rotations about a lateral axis and a longitudinal axis) that
      can be controlled independently. Good trot and pace gaits similar to
      those obtained using angular velocity outputs evolved only in three
      out of ten trials. Typically, the networks produce oscillations that
      are so fast that the legs seem to vibrate and the gaits look
      unrealistic:

      http://www.cs.utexas.edu/users/vkv/quad-universal-angleoutputs.mp4

      So in my setup, good gaits are easier to evolve when networks output
      desired angular velocities. I think it is because such networks allow
      us to control angular velocities directly, resulting in leg movements
      that are of the right speed for producing good gaits.

      Vinod


      At Fri, 27 Feb 2009 03:59:44 -0600,
      Vinod K. Valsalam wrote:
      >
      >
      > Ken,
      >
      > The ODEs of the coupled oscillator system express time derivatives of
      > the state variables as a function of those variables. Therefore, when
      > the outputs are derivatives of the inputs, the network corresponds
      > directly to the ODEs, i.e. the network has the mathematical form of a
      > coupled oscillator. I suggested using angular velocities as network
      > outputs to take advantage of this mathematical formalism. I thought
      > some more about whether we would still have similar advantages if the
      > network outputs desired angles instead of angular velocities. It
      > turns out that such a network represents an approximation of the ODEs.
      > To elaborate, let us write the derivatives in discrete form. For
      > example,
      >
      > .
      > x = F(x)
      >
      > becomes
      >
      > (x_(n+1) - x_n)/(t_(n+1) - t_n) = F(x_n)
      >
      > for the nth time step. For constant step size, we can rewrite it as
      >
      > x_(n+1) = G(x_n)
      >
      > We can represent such equations using a network that takes the current
      > joint angle as input and produces the desired angle for the next time
      > step as output. So such a network should work as an approximation of
      > the coupled oscillator system. I will run some experiments to find
      > out how well this approximation works in practice.
      >
      > Vinod
      >
      >
      > At Fri, 27 Feb 2009 02:13:44 -0000,
      > Kenneth Stanley wrote:
      > >
      > > Vinod, thanks for the detailed reply; it was very informative. One
      > > issue on which I am still unclear is why it is important that the
      > > outputs be derivatives? Why do you say that that is critical? For
      > > example, if I had a system that took angle as input and output desired
      > > angle (like Jeff's), could not such a system form coupled oscillators
      > > just as well? If not, what makes it more effective when outputs are
      > > desired velocities? Is it simply that velocities require less
      > > accuracy to express than target angles?
      > >
      > > ken
      > >
      > >
      > >
      > > --- In neat@yahoogroups.com, "Vinod K. Valsalam" <vkv@...> wrote:
      > > >
      > > > At Tue, 24 Feb 2009 18:24:54 -0000,
      > > > Kenneth Stanley wrote:
      > > > >
      > > > > Vinod, could you define "coupled non-linear oscillators" more
      > > > > specifically? What are the necessary and sufficient conditions for
      > > > > something to be considered a coupled non-linear oscillators?
      > > >
      > > > Hi Ken! The coupling here means that the oscillators influence each
      > > > other's behavior. Let me use the term "coupled cell system" to be
      > > > more precise. A coupled cell system is a collection of cells, where
      > > > each cell i is a dynamical system with state x_i. If cell i is
      > > > coupled to another cell j, then it means that the state of cell i
      > > > depends on the state of cell j. Such a system is represented by a
      > > > system of ODEs. For example, the ODEs for a system with two cells
      > > > that are coupled to each other can be written as follows:
      > > >
      > > > .
      > > > x_1 = F_1(x_1, x_2) ........ cell 1
      > > > .
      > > > x_2 = F_2(x_2, x_1) ........ cell 2
      > > >
      > > > The LHS of the above ODEs represent the time derivatives of the state
      > > > variables, and the functions F_1 and F_2 represent the internal
      > > > dynamics of the cells. The linearity or non-linearity of the system
      > > > is determined by the nature of F_1 and F_2.
      > > >
      > > > The term "cell" is used instead of "oscillator" in the above
      > > > terminology because it is not necessary for individual cells to be
      > > > capable of producing oscillations. However, the coupled cell system
      > > > as a whole can display oscillatory behaviors. More importantly,
      > > > making some of the cells and couplings identical can constrain the
      > > > cells to oscillate synchronously or with constant phase relations with
      > > > each other, a property that is useful for modeling gaits. For
      > > > example, making the cells and couplings identical in the above
      > > > two-cell system results in F_1 = F_2 = F. It is then possible to show
      > > > that functions F exist for which solutions x_1 and x_2 of the system
      > > > are periodic and half a period out of phase with each other (see [1]
      > > > below for details).
      > > >
      > > > Gaits are produced by assigning these cells to control the legs of a
      > > > robot. But how do we find an appropriate function F? In my GECCO
      > > > paper, I found F by representing it as a neural network module and
      > > > then evolving it. That is, the coupled cell system is implemented as
      > > > a neural network controller, where each network module represents one
      > > > ODE of the system. The state variables x_i are the leg joint angles.
      > > > Thus the network takes joint angles as input and produces desired
      > > > joint angular velocities as output. This formalism has the following
      > > > advantages:
      > > >
      > > > 1. Theoretical understanding of the possible gaits. Coupled cell
      > > > systems can be designed that model central pattern generators in
      > > > animals, producing symmetric, animal-like gaits.
      > > >
      > > > 2. Modularity: The coupled cell system I used for quadrupeds has
      > > > four identical cells/modules that differ only in the permutation
      > > > of inputs they receive.
      > > >
      > > > 3. Simple feed-forward neural network implementation, i.e. no need
      > > > for leaky integrators or recurrency. Notice that the sigmoid
      > > > activation function of the neurons in the network provides any
      > > > necessary non-linearity.
      > > >
      > > > However, I had to manually specify the modules and the permutation of
      > > > inputs to each module. It would be cool if HyperNEAT can evolve that
      > > > specification automatically.
      > > >
      > > >
      > > > > For
      > > > > example, I am assuming that either leaky or non-leaky neurons can be
      > > > > part of a coupled non-linear oscillator, or is it somehow more
      > > > > appropriate for the neurons to be non-leaky? I guess I am curious why
      > > > > having a non-leaky neuron would be the most favorable choice in such a
      > > > > model, or whether it is somehow a matter of definition.
      > > >
      > > > Notice that my description above did not make any assumptions about
      > > > leaky or non-leaky neurons. Either type should be OK. I used
      > > > non-leaky neurons because they are simpler and sufficient. I did not
      > > > experiment with leaky neurons.
      > > >
      > > > >
      > > > > Also, what are the minor adjustments to the substrate that you mention
      > > > > that would create this kind of system?
      > > >
      > > > Essentially, the substrate needs to implement the ODEs of the coupled
      > > > cell system, i.e. substrate outputs must be the time derivatives of
      > > > its inputs. This condition is satisfied if inputs are joint angles
      > > > and outputs are desired angular velocities. The minor adjustment to
      > > > Jeff's substrate that I mentioned was to interpret outputs as desired
      > > > angular velocities instead of desired angles. In principle, inputs
      > > > besides joint angles are also not necessary for generating gaits.
      > > > However, the other inputs he used (roll, pitch, yaw, and touch) may be
      > > > useful for more complex behaviors that require such additional sensory
      > > > inputs.
      > > >
      > > > >
      > > > > In my experience, the leaky neurons also can produce oscillations
      > > > > reliably, but I am not sure if that is actually anything different
      > > > > from what you are describing or just another instance of the same
      > > > > phenomenon.
      > > > >
      > > >
      > > > As I mentioned above, a coupled cell system is a dynamical system.
      > > > Since networks of leaky neurons can approximate any dynamical system,
      > > > you are right that it is another instance of the same phenomenon.
      > > > However, the coupled cell system framework allows us to reason about
      > > > the high level properties of the system such as synchronicity and
      > > > phase relations that are useful for gait generation, producing the
      > > > advantages I listed above. As a result, evolutionary search can be
      > > > biased to discover robust and effective gaits more easily.
      > > >
      > > > References:
      > > >
      > > > There are several papers by Stewart, Golubitsky and others on the
      > > > theory of coupled cell systems and how they can be used to model
      > > > animal gaits. For example, see the following:
      > > >
      > > > [1] I. Stewart, M. Golubitsky and M. Pivato. Symmetry groupoids and
      > > > patterns of synchrony in coupled cell networks. SIAM
      > > > J. Appl. Dynam. Sys. 2 (4) (2003) 609-646.
      > > > http://www.math.uh.edu/~mg/reprints/papers/groupoid_siam.pdf
      > > >
      > > > [2] J. J. Collins and I. N. Stewart. Coupled nonlinear oscillators and
      > > > the symmetries of animal gaits. Journal of Nonlinear Science,
      > > > 3(1):349--392, 1993.
      > > >
      > > > My GECCO paper also has a background section discussing the coupled
      > > > cell system I used for my quadruped robots.
      > > >
      > > > Vinod
      > > >
      > > >
      > > > > Thanks,
      > > > >
      > > > > ken
      > > > >
      > > > > --- In neat@yahoogroups.com, "Vinod K. Valsalam" <vkv@> wrote:
      > > > > >
      > > > > >
      > > > > > Hi Jeff,
      > > > > >
      > > > > > Interesting work! I was also curious to see how HyperNEAT would
      > > > > > perform on this domain. The videos of quadruped and hexapod gaits I
      > > > > > evolved, and the paper I wrote with Prof. Risto Miikkulainen for
      > > last
      > > > > > year's GECCO are available here:
      > > > > >
      > > > > > http://nn.cs.utexas.edu/keyword?modularne
      > > > > >
      > > > > > With regard to the discussion about generating oscillations, I used
      > > > > > neither sine wave as input nor leaky integrators. Instead, neural
      > > > > > network controllers with standard sigmoid neurons were
      > > modularized to
      > > > > > behave as coupled non-linear oscillators (coupled cell systems). As
      > > > > > explained in the paper, and as Jean-Baptiste mentioned in an earlier
      > > > > > post, such oscillators can produce synchronous and phase-related
      > > > > > periodic behaviors suitable for generating gaits. They are easy to
      > > > > > evolve and produce animal-like gaits such as the pronk, pace, bound
      > > > > > and trot for quadrupeds.
      > > > > >
      > > > > > With only minor adjustments to your setup, you can convert your
      > > > > > substrate configuration to represent non-linear oscillators. In
      > > fact,
      > > > > > you would get a configuration similar to my modular controllers by
      > > > > > restricting the network inputs to just the joint angles and
      > > producing
      > > > > > angular velocities instead of angles as outputs. HyperNEAT
      > > would then
      > > > > > have to evolve the modularity that I specified by hand. I think
      > > that
      > > > > > would be an interesting experiment to run, and if successful would
      > > > > > eliminate the need to specify the sine input. BTW, did you find
      > > that
      > > > > > the other inputs (i.e. pitch, yaw, roll, and touch) were
      > > necessary to
      > > > > > evolve good gaits in your experiments?
      > > > > >
      > > > > > Vinod
      > > > > >
      > > > >
      > > > >
      > > > >
      > > > >
      > > > > ------------------------------------
      > > > >
      > > > > Yahoo! Groups Links
      > > > >
      > > > >
      > > > >
      > > >
      > >
      > >
      > >
      > >
      > > ------------------------------------
      > >
      > > Yahoo! Groups Links
      > >
      > >
      > >
      >
      >
      > ------------------------------------
      >
      > Yahoo! Groups Links
      >
      >
      >
    • Jeff Clune
      ... I did see that. But I read somewhere else that they were about to come out with one around 3-4k. That s still a lot, but at least the price is coming down.
      Message 42 of 42 , Mar 26, 2009
        > Wow. Did you see the price for Nao ($15,000)? I assume if you are going to
        > keep research in the realm of a simulated environment, that is not relevant.
        > But us home researchers are most assuredly out priced on this robot. I would
        > rather spend the cash on E-Bay and buy an Aibo.

        I did see that. But I read somewhere else that they were about to come out
        with one around 3-4k. That's still a lot, but at least the price is coming
        down.

        > I see your point with the inaccuracy of the simulation. But, if the network
        > is evolved to handle the simulated environment, its adaptability should
        > allow for minor deviations between simulation and physical, right? I think
        > this would be even more effective if some of your inputs are the current leg
        > positions. Hmm.. I am going to play with this and see what shakes out.

        If you have any luck please let me know. I am very interested in whether it
        works for you.

        As to your question, I am not evolving my robots with noise in the system,
        so they may have evolved gaits that rely on that precision. My guess is that
        the evolved gaits would not immediately work in the noisy world. If you
        continued to evolve on the actual robot you may see evolution figure out how
        to move well in the real world, but that would require many trials on your
        actual robot. The best plan is to try to have the simulator very accurately
        reflect the real world before evolving the controller and transferring it.

        > Please forgive my moronic assumptions here. I am far more used to
        > programming my quad with straight forward code, and only recently started
        > planning on implementing something similar to the work you did. And thanks
        > for that by the way. It re-sparked the project for me.

        No problem. Glad to hear you liked it. Please keep us updated on your
        project.

        Cheers,
        Jeff


        >
        > From: neat@yahoogroups.com [mailto:neat@yahoogroups.com] On Behalf Of Jeff
        > Clune
        > Sent: Tuesday, March 24, 2009 4:20 PM
        > To: neat@yahoogroups.com
        > Subject: Re: [neat] Re: Evolving Coordinated Quadruped Gaits with the
        > HyperNEAT Generative Encoding
        >
        >
        >
        > Hello Erik-
        >
        > Thanks for the suggestion. I have read that it takes a lot of work to make a
        > simulator accurate. My guess is that without that substantial investment,
        > controllers evolved in simulation would not work very well on the actual
        > robots. It continues to surprise me that no robots exist with simulators.
        > Hopefully someone will put one out soon. The Aldebaran Nao, which is
        > replacing the Aibo for RoboCup, has two simulators, but I do not know if
        > they are accurate.
        >
        > In any case, I appreciate you keeping an eye out. Let me know if you see any
        > that have simulators.
        >
        > Cheers,
        > Jeff Clune
        >
        > Digital Evolution Lab, Michigan State University
        >
        > jclune@... <mailto:jclune%40msu.edu>
        >
        >> From: Erik <erikcss@yahoo. <mailto:erikcss%40yahoo.com> com>
        >> Reply-To: "neat@yahoogroups. <mailto:neat%40yahoogroups.com> com"
        > <neat@yahoogroups. <mailto:neat%40yahoogroups.com> com>
        >> Date: Mon, 23 Mar 2009 00:22:58 -0700
        >> To: "neat@yahoogroups. <mailto:neat%40yahoogroups.com> com"
        > <neat@yahoogroups. <mailto:neat%40yahoogroups.com> com>
        >> Subject: RE: [neat] Re: Evolving Coordinated Quadruped Gaits with the
        >> HyperNEAT Generative Encoding
        >>
        >> Jeff,
        >>
        >>
        >>
        >> You may want to take a look at the Quad from crustcrawler.com. It does not
        >> have a simulation for it, but I have one of these and use it often. It
        > would
        >> not be too difficult to create a simulation for it.
        >>
        >>
        >>
        >> _____
        >>
        >> From: neat@yahoogroups. <mailto:neat%40yahoogroups.com> com
        > [mailto:neat@yahoogroups. <mailto:neat%40yahoogroups.com> com] On Behalf Of
        > Jeff
        >> Clune
        >> Sent: Friday, February 20, 2009 2:07 PM
        >> To: neat@yahoogroups. <mailto:neat%40yahoogroups.com> com
        >> Subject: Re: [neat] Re: Evolving Coordinated Quadruped Gaits with the
        >> HyperNEAT Generative Encoding
        >>
        >>
        >>
        >>> Yes. I'm just thinking broadly of the commercial viability of a cheap
        >>> leg based locomotion controller. Wheels are of course really good for
        >>> many situations in the modern world, but legs still win in all but the
        >>> most artificial (roads and level floors) situations. I expect there
        >>> are military and commercial applications for small to large scale
        >>> legged vehicles for carrying payloads e.g. up a mountain/hillside,
        >>> through boggy land, stuff like that. I just see it as an area with a
        >>> large short term commercial potential in comparison to some of the
        >>> other typical EC problem domains we all know and love.
        >>
        >> I fully agree with you. I wonder how long it will be before we see such
        >> robots carrying gear around for us. Big dog certainly implies that it
        > won't
        >> be that far off.
        >>
        >>>> Do you know of any robots that can be bought and have a high-fidelity
        >>>> simulator (preferably in ODE)?
        >>>
        >>> Sorry no.
        >>
        >> I continue to be shocked by this. I feel like there have to be lots out
        >> there, but at this point I have asked the NEAT community and the ODE
        >> community, and searched a ton on Google, and no one seems to know of any.
        >>
        >> Has anyone out there used Webots? I think they have a simulation of a
        >> Bioloid quadruped in there that you can buy. At least, I think you can buy
        >> the building blocks and assemble it.
        >>
        >>> I'm not getting any clear thoughts on why the period would evolve to
        >>> be so slow. The only suggestion I have is that maybe the CPPNs weren't
        >>> able to effectively coevolve these two disparate features - a gait
        >>> controller and a single wave period value. Using the CPPN in this way
        >>> is probably just a cheap and easy way of evolving a period value, with
        >>> the ideal solution being a completely independent period value bolted
        >>> onto the NEAT genome.
        >>
        >> I agree with you. I have thought many times that it is the fact that I am
        >> asking the CPPN to do two different things which is causing the problem. I
        >> like your suggestion, and have had it on my to do list for a while
        > (bolting
        >> an extra, one allele, real value genome onto each CPPN genome and see how
        >> that works). However, given how far away the CPPN coordinates I am asking
        >> for the period are from the joint inputs/outputs, I am surprised it is
        >> difficult for the CPPN to deal with the separate objectives. But your
        >> suggested experiment will test these issues and should be performd. I'll
        > let
        >> you know when I get around to it.
        >>
        >> Thanks (again) for the suggestions.
        >>
        >>
        >>
        >
        >
        >
      Your message has been successfully submitted and would be delivered to recipients shortly.