Movement Planning as Evolution?

Evolutionary algorithms solve a problem by maintaining a population of variant partial solutions and applying recombination operators to them. Those operators can be considered valid, or available operations in a space of configurations. Our brick structures algorithms are solving problems of spatial arrangement, subject to buildability restrictions, starting from a known initial configuration and advancing, one step at a time, by legal transformations. The simulation enforces that each step is physically correct.

The implication is that the succession of genetic transformations that yield to a final stage can be considered a plan. Problems of planning for spatial arrangement are classic in AI [35]. One plausible future application of structural evolutionary algorithms is to adapt the recombination operations to reflect valid reconfigurations of a modular metamorphic robot. Problems of robot locomotion for example could be solved by evolving a plan for the desired final configuration from the starting one.

We ran an exploratory experiment which evolves an imaginary amoeba-like creature made of Lego bricks (fig. 2.35). Once a goal state is obtained, the ``family tree'' from the initial to final configurations represents a sequence of valid transformations.

  

Figure 2.35: An imaginary Lego creature evolves a plan to locomote between islands by expanding and contracting its body in ``amoeba'' fashion. Each step involves adding, deleting or sliding a limb, as induced by mutations. Recombination works as macro operator.

The mutation operations are interpreted as the ``valid actions'' of the creature (i.e., extending, retracting or displacing limbs) and recombinations amount to macro operators, chaining a sequence of actions.