Illuminated Manuscripts

Finally setup a wiki (based on MediaWiki) to replace the blog.

Check it out: http://www.luminousbeings.com/

Physical Human Movement Sketches

Fast Muscles, Rutgers.
- some focus on biological accuracy.
- Previous:
- Lines of Force; fail with large muscles with largg contacts.
- FEM/FVM. Difficult to *acquire*
- Approach: "Strand" - fiber-like
- "Unconditionally stable"
- Speed vs. visual accuracy vs. kinematic accuracy
- Cosserat theory of elastic rods. Rubin 200, Pai 2002
- Fibers are Segments divided by nodes. Nodes drive free-form controls that model the muscle volume.
- Separate models for tendons and muscles
- Hill-type muscle model -- Zajac 89., Teran 2003
- first-order numerical method
- "SVD" collisions become contact become equality constraints
- KKT

Interactive and Reactive Dynamic Control; Ari Shapiro
"Fah lout sauce"

"reactive skills"
control methods: kinematic(modifying mocap) vs. dyanmic control
"Fully interactive character"
- "mocap is probably necessary" "needed to do the complicated things that we want (the character) to do"
- "exploration" sytaste of physical control
- Mandel 04, Master's Thesis: Reactive Behaviors

ban De Panne - 2003, ski simulated; 2005, Zhao ***
"virtual humanoid"

RI: training wheels for learning

"i'd love to incorporate massive-like approaches"


Fast Volume Preseveration for Realistic Muscle Deformation.
RI: maybe a variation on the verlet tertrahedron would work for volume preservation in simulated muscles?

AI Characters Panel at Siggraph

Andrew Stern - Facade - Procedural Arts (grandtextauto.org)
Next-gen game machines will spend most of the CPU on feeding the graphics engines-- leaving little behind for AI.

"Balance of visual fidelity and behavioral fidelity." By design.
---

Animation-guy. EA Sports. Canada.
"Issues we need to overcome."
"What does the viewer assess?" -- 1) apperance 2) movement, locomotion, 3) performance.

next-gen: super-realistic visual characters, but the same AI

- how should an AI react to a situation
- how is that reaction conveyed?
- ramifications of the choices.

Next Gen AI: Locomotion and Performance
- Locomotion. "moments of realiaty interrupted by bad transitions" ignoring physics, inertia, etc.
- On ice! Ice skating physics sim :-) what else? swimming?
- attribute-based motion: did he get tripped?
- the "tough part with AI is that you only have so many mo-cap choices-- if you only have one fall, can't distinguish between between pissed off for being tripped or diving for a tackle, or falling shamefully
- anticipation
- "a cycle is a necessity"

Performance.
- situational awareness.
- unique reactions-- star player-cocky on scoring a goal; rookie-excited as hell on a goal.


"Get away from sewing together clips of motion."
"simulation and procedural techniques to create motion"
"animators teach their characters how to behave"
"creating individual behaviors for hundreds or thousands of characters in a game has to be done procedurally"

"first concern of game developers: testing" (does that matter so much for locomotion? presumably not) Moving more toward automated testing. Maybe GAs for test suites? :-)

Major dichotomy: data-driven vs. first-principle results.

In a FPS-- expressing fear vs. boldness: maybe not too hard to extract from player movement. How should teammates respond.

jason oseepa - "Stop Staring"

"motion capture will be just another training technique for the procedural motion"

Vesicles

Why do neurons have synapses at all? Why not just wire dendrite to axon directly?

Vesicles discretize synaptic events. The "quantal count" is the number of vesicles per synaptic event; by interposing synapses, rather than just passing the electric potential directly, the signal is rendered digital.

Presumably a more important aspect, synapses allow the trans-cellular environment to affect the signal, e.g., NO.

Transcription Factors and Learning

What's the role of transcription factors (e.g., CREB) in LTP? Looking into Kandel's work for the 2000 Nobel prize.

Random Thought

A search algorithm layered on top of (or underneath, I suppose) an evolutionary search that finds areas of broad neutrality and pushes the population out to the edges by way of a gradient search.

If a mutation is found to be nearly neutral, pause evolution and probe in the direction of the mutation, looking for the range of neutrality. Then spawn children within that range (stocasticly or evenly distributed).

Rough idea: more efficiently take advantage of neutral planes.

Although it would surely suck, I'd be interested in watching this method taken to the extreme-- that is, doing an exhaustive search for neutral areas periodically. Perhaps a reasonable approach when evolution stalls.

To Read

Fitness Landscapes and Evolvability. Smith, Husbands, Layzell, O'Shea. Evolutionary Computation 2002.

A Small-systems Approach to Motor Pattern Generation. Nusbaum, Beenhakker. Nature 2002.

"Freezing and Freeing of Degrees of Freedom"

An interesting paper in Adapative Behavior, "Motor Skill Acquisition under Environmental Perturbations: On the Necessity of Alternate Freezing and Freeing of Degrees of Freedom" (Berthouze, Lungarella; Neuroscience Research Institute, Tsukuba, Japan). I'd like to try to conceive of the "freezing and freeing" approach along the lines of neutral mutations. I realize it's a bit far-fetched, especially in the paper's particular focus on infant development, but I'm interested in ways to coerce a system to be fully traversable by nearly neutral mutations, and this is perhaps good inspiration.

Realistic Neuron Models

After reading "An Analysis of Neural Models for Walking Control" I've been interested in looking more carefully at neuron models that go beyond the sigma-in-a-circle that ANN research usually considers.

NEURON and GENESIS are too big software packages that seem popular. NeuroConstruct looks nice as well.

(One confounding factor worth considering is that there are so many different types of neurons with such different properties. Purkinje cells, Pyramidal cells, Granule cells, "mossy fibers", etc.)

Intercellular connections: Gap junctions. Chemical synapses.


MorphML

Quote of the Day

The secret to understanding complicated things is knowing what not to look at.

- Gerald Jay Sussman

Objectives

I'm thinking seriously about the directions I'd like to pursue in the next six months or so. Some of these are straight-forward and easily testable, some are wild ideas or random shots-in-the-dark.

• Modular vs. centralized controller. Using two instances of the same evolved controller, one for each lateral side, had a dramatic effect on evolvability of biped.
• Does communication between instances help? (eg, a shared connection)
• Will a smaller grain work better? Even unintuitive approaches like an instance for each joint might be interesting.
• More complex neuron models. A recent paper suggests that this is indeed an important factor.
• Beer/Leaky neurons (CTRNNs), 1st-order ODE.
• Taga, 2nd-order ODE.
• Ekeberg, 3rd-order ODE. Reeve's 1999 thesis suggests this model is best for oscillation.
  
• A mix of different neuron models. Gut feeling that this is the most promising.
  
• Different schemes for linkage between networks. People seem fixated with changing weights of semi-static connections, but other approaches, like Gas Nets, are very interesting.
• Development/Embryogeny. Haven't looked into this much, but Bongard's work was pretty compelling, especially when combined with fluid or position-based connections/excitation transfer.
• Related, continuing with the "clump" approach to pattern generation. The echo-state network idea seems wonderfully suited to developmental approaches.
  
• Properties of locomotion space for different neural models. CTRNN-XOR space was looked at in some depth by USussex folks. Clearly need to investigate techniques for characterizing the space, esp interested in relation to neutral networks.
• Related, is cross-over really important? I'm still looking for alternative variatoin operators.
  

Neutral Networks

My very rough idea of Neutral Networks is that they are a special class of problem where you're guaranteed that you can always move "sideways" in at least one-dimension in the fitness space. That is, for any individual, there's always at least one direction to go that doesn't reduce your fitness.

The interesting part is that many systems, such as evolved neural networks, have the hope of being at least a little like ideal neutral networks, and so may be good problems to solve via evolution. Indeed, supposedly, if a problem behaves according to the rigorous definition, a global minima will be found.

All this got started with Motoo Kimura, Eigen and Schuster. Looking at RNA "folding landscapes" (not the proteins generated by the code, but the actual RNA molecule itself, (what's the jargon for it??)) as netural networks.

All this seems to have started with Lionel Barnett's 1997 MSc dissertation "Tangled Webs: Evolutionary Dynamics on Fitness Landscapes with Neutrality" (word) (ps). I find it wonderfully readable and inspiring. Here's some quotes:

Comparatively recent developments in evolutionary theory and molecular biology have all pointed to the importance of selective neutrality as a significant factor in evolutionary dynamics. This work includes Motoo Kimura's Neutral Theory of molecular evolution, Manfred Eigen's analysis of molecular "quasispecies" and recent developments in the understanding of RNA evolution both in vitro, in simulation and analytically. A picture emerges of populations engaged not in hill-climbing but rather drifting along connected networks of neutral genotypes, with sporadic jumps between networks. These neutral networks are of particular significance if they "percolate" the landscape - i.e. they come arbitrarily close to almost every other neutral network - for this raises the possibility that (given enough time) genotypes of almost any possible fitness value can ultimately be attained by the population. The scenario of a population trapped on a local hilltop vanishes.

and he also makes a point that has bugged me since first reading about GA's:

...we limit our "genetic operators" to mutation alone. Our genotypes are all haploid and reproduction is asexual. This merits some comment. In the GA literature dating back to John Holland there has been a perception of recombination (crossover) as the driving force behind evolutionary search, with mutation taking a back seat as an insurance policy against permanent allelic loss. It is not clear why mutation has been thus relegated, nor that recombination is necessarily effective in search. From the biological point of view there are many organisms for which recombination rarely or never occurs during reproduction. Molecular biology, furthermore, offers many scenarios of non-recombinative reproduction.

Finally, Sussex EASy's Bibliography of Neutral Networks (way out of date), and some high-level, but good lecture notes from a class there. (Use IE. Really, Firefox 1.0.4 didn't work)

Locomotion-specific Neuron Models

What neuron model should be used for Locomotion tasks? Is there a big difference? Does the increased parameter space overwhelm the gains of autonomous periodicity? That's the topic of An Analysis of Neural Models for Walking Control and, at least for quadraped locomotion, the answer seems to be that more complex neurons are a gain overall.

Neural models that they consider:

• Threshold.
• Sigmoidal.
• Leaky-integrator/Continuous-time, or first-order ODE. (Beer) (note that self-connections are needed for oscillations). Funahashi and Nakamura. Did Beer use plastic weights? Do R&H? Is it advantageous?
• Taga (10). Second-order ODE, basically an extension of leaky-integrator with an additional, coupled 1st-order ODE.
• Ekeberg (12). Three state version, 3rd-order ODE. Developed for analysis of the lamprey spinal cord networks that controlling swimming.

On a similar note, Center-Crossing Recurrent Neural Networks for the Evolution of Rhythmic Behavior shows that Center-crossing CTRNNs work better for locomotion than randomly aligned CTRNNs.

I'd like to see some comparisons between CC-CTRNNs and Taga's and Ekeberg's models as well.

The details of Reeve's and Hallam's setup are in Reeve's PhD Disseration at Edinburgh, Generating Walking Behaviors in Legged Robots.

Finally, what I keep expecting to find is evolution of a linear combination of sine functions. I mean, if you just want a stable walker, wouldn't this work nicely?

Also worth looking at CiTRuS: The Continuous Time Recurrent System, from Robert Vicker at Sussex.

Multiple Instances of a Single Controller

In ELSE, evolving one controller that handled all the inputs and outputs was pretty much a dead-end. Instead, evolving a single controller network and making two "instances" of it, one for the left side and a mirrored one used by the right side. (need to measure this and the effect of adding a communication connection)

It turns out that insects may do a similar thing. Holk Cruse, according to this the ANWM Seminar notes, "found that insects, which have many legs, do not use a central processor to keep track of all the movements of their multiple legs. Instead local interactions between sensory motor reflexes enable complex walking behaviors to emerge."

Vaughan's using Bilateral-symmetry: BSSNN

http://www.droidlogic.com/sussex/adaptivesystems/Arm.pdf

Where's the Interest in Mapping Fitness Functions of Real Problems?

It seems to be generally assumed that one primary difficulty in applying evolutionary methods is defining a smooth fitness function that avoids local minima as possible. Even the best methods, like NEAT, stagnate as some point. I'm interested in looking at these places in the fitness landscape-- places where evolution isn't able to make further progress. Perhaps even mapping them out. Maybe even generating or co-evolving fitness functions to help find easily understood evolutionary traps. It would probably yield nothing intelligible, but possibly trying to characterize fitness functions by looking at where they trap different representations.

Here's an example looking at CTRNNs and XOR. I find it most striking that there isn't anything familiar-looking in his graphs. Wouldn't you think XOR would be simple? And since it really isn't, what is a simple (but at least slightly non-trival) problem for evolved NN's or CTRNN's?

LT Research Thoughts

Generalize both the code and the approach of ELSE to support the evolution of many behaviors using different approaches (e.g., evolved periodic functions, CTRNNs, echo-state networks, etc.). Possibly fall back to working with something more stable, eg. quadrapeds or maybe even worms/snakes.
- Implement from-scratch version of CTRNN-evolver based on NEAT ideas. Abstract evolver from evolved (how realistic? tricky interface to define and still support things like NEAT)
- upgrade to ODE 0.5 (or possibly look into coding up a Verlet-based PE?)
- add config scripts for generating skeletons, bodies, joints and motors.
- add script interface for fitness and short-circuit evaluation
- add script interface for "supports" as a function of time

Use PF's learned-controller-selection approach to choose which evolved controller to use at any point in time. Probably, just add evolved controllers to DANCE (plus maybe add ODE to DANCE or ?? to ELSE).
Co-evolve controller-selection (dispatcher?) with controllers. How to structure fitness s.t. controllers don't become muddled up?

Developmental Neural Networks

Just stumbled upon this page:

This project models the rules of biological self-organisation that can generate neural circuits. Rules governing development are used to "grow" the inter-connections between the neurons. Currently this development model "grows" 3 D layers of Neural Networks using local chemical gradients emitted by neurons that influence both the growth direction of other neurites (axons and dendrites) and their propensity to split. It has been used to generate a large-scale structure based on a biologically plausible model of a retina that does edge detection and, for individual neurons, to produce the appropriate spiking behaviour when presented with a stimulus. A genetic algorithm is used to search the parameter space to determine the best parameter values for the development rules.

A multi-compartmental neuron simulator (called NEURON), that used partial differential equations, was used when investigating the neuron firing patterns. This model is too slow for networks of neurons and a faster simulation, that uses an adaption of a finite state machine to tree structures, has been partially developed.

The PhD programme will either:

1. Complete the new multi-compartmental neuron simulator and integrate it with the developmental model. The final combined models will be used to look at the effect of dendritic geometry on function, and possibly to define classes of dendritic geometries.
or

2. The model for growing neural networks will be extended to include the concept of genetic regulatory networks. A genetic regulatory network is the intricate and recursive network of activation and repression mechanisms formed by proteins that act on genes to determine whether and when they should generate other proteins. As such it can be used to model interactions between the parameters that control the developing neural network over time.

An interest in neuroscience and biology would be beneficial for this project.

To discuss this project please contact Rod Adams.

Automatic Balance in the Face of Motion

I've been thinking of a neato (hypothetical) controller that would be automate the balance shifts that should occur when animating. Consider two animations, the classic walk cycle and a wave action. IRL, the walk motion should be affected by the wave in that the balance is slightly shifted, and likewise the wave is affected when walking because the hand should swing around during balance.
This would then be in the province of the RT animation blender-- to dynamically shift the body, slightly, in order to maintain balance.

Random thought: some fun could definitly be had by giving the skeleton a cane or crutches and seeing what motion emerged.

Some (as yet unread) references:

• G. Taga, 1997, A Model of Integration of Posture and Locomotion, Proceedings of International Symposium on Computer Simulation in Biomechanics.
• A. Kun and W. T. Miller, III, Adaptive Dynamic Balance of a Biped Robot using Neural Networks. Proc. IEEE Int. Conf. on RA, pp. 240--245, 1996
• Kun A. L., Miller W. T. (1997), Adaptive Static Balance of a Biped Robot Using Neural Networks, Proc. of the Int.
• 
  
  

Distributed ELSE

The physical-simulation evaluation is an obvious choice for distributing.  Roughly, the inputs are:

- the physical sim parameters (gravity, harness, obstacles, friction, time-step, collision parameters, etc),

- the character geometry (limb and joint type and positions, angle limits),

- the character actuators/muscles (strength, PID-params, CFM),

- the controller neural network (or, alternatively, the genome.  It seems cleaner to keep the genotype->phenotype piece out of the client.)

 

The per-frame outputs would be (this is optional, but good for keeping tabs):

- instantanous joint angles, CoG.  (to allow drawing).  Surely there's some compact, standard format for this kind of "motion capture" data.  (want both q and q', plus maybe torques as well.)

- current fitness

 

The per-evaluation outputs would be:

- final fitness

Other Controllers

Random thought:  physical simulation is by far the slowest part in ELSE.  Implicit integration would both speed things up nicely and help stabilize it numerically, reducing the number of checks and so speeding it up further.  But implicit methods don't like impluse-style forces like collisions.

 

So what about flying and swimming behaviors?  They've been done a bit, but not so well.  I'm not sure about the trade-offs, but I'm thinking about a fluid simulation to evolve bird or insect flight controllers.  This would be interesting because, 1) as far as I know, insect flight is still difficult to understand by analysis, 2) implicit fluids would be stable and reasonably fast (wonder what the Korean evolved flight team used for a physics model?), 3) it might be visually impressive: large birds due to grace and small insects due to the strangeness of flight technique.  Though insects, esp, might rely on far too subtle fluid properties (say, micro vortices) that wouldn't be tractable to simulate naively.

 

I don't know much about fluids outside of reading Jos Stam's papers from Siggraph.  It'd be critical to get realistic forces acting on the wing surfaces from the fluid; not sure if the current fast fluid sys techniques do that much.

Levels of Models in Character Animation

In essence, computer-generated character animation is attempting to mimic the actions and behaviors, down to the nuances, that real, live humans have. So to improve the resulting animation, we need to look hard at the various models we use to see where improvement can be made.

In PF's doctoral work, he uses a SVM to choose, at run-time, a low-level, specialized controller from a pool of available controllers. Each of these controllers is effectively a small program that can look at inputs and actuate motors. The SVM is acting to choose among zombies.

Some possible levels to consider:
- Neuron. Spike vs. CT, etc.
- Neural Network. Learning, construction, evolution, by-hand design.
- Geometrical. The shape and length of limbs, angles of rotation.
- Physical. Mass distribution.
- Actuator. Strength of muscles, location of action. PIDs vs. complex muscle-tendon-ligament.

- Joints.  Ball-and-socket and hinge vs. complex, multi-boned configurations. 

 

An evolutionary approach seems like a good match with making joint models more complex, since it would increase realism without too high (or perhaps any) cost in larger state space.  Probably the initial candidates would be the hip and lower spine-- the swagger/butt swing is a big part of the apparent realism of a walk.

The Neuronal Basis for Consciousness

I spent a couple hours in the bookstore reading a book that follows Prof. Koch's Caltech course CNS/Bi 120, The Neuronal Basis for Consciousness. Although it went a bit more in depth than I could absorb just sitting in the store, but it was highly useful to me for introducing a novel and consistent vocabulary for talking about actions, perceptions and awareness. "Zombie", as defined by Koch, is a sub-awareness action taken without conscious awareness. Something like picking up a glass or shifting gears in a manual car. Zombies tend to come from repetitive training.
I'm quite looking forward to reading the full book and watching the lectures.

Notes on Mutants

Some interesting tidbits, though most thrown out without justification or reference, from Mutants:

• A polymorphism is a mutation that is common (enough) in the population.  Roughly figured around one percent of the population.  Using this definition, at least one polymorphism is present in about 65% of all genes.

• Each new embryo gets about 100 mutations during copying.  Of these, four will imply changes in resulting proteins.  Of these four, three will be harmful.