A General Rhythmic Pattern Generation Architecture for Legged Locomotion - Advancing Artificial Intelligence Through Biological Process Applications - page 207

gait transitions. Its primary weakness, however,
is that the physiological relevance of the relative
phase coupling terms is unclear.

A Primer to SER and SMER
Algorithms

Scheduling by Edge Reversal (SER)

A Group-Theoretic Approach

Consider a neighbourhood-constrained system
comprised of a set of processes and a set of atomic
shared resources represented by a connected graph
G = ( N,E ), where N is the set of processes and
E the set of edges defining the interconnection
topology. An edge exists between any two nodes
if and only if the two corresponding processes
share at least one atomic resource.
SER works in the following way: starting from
any acyclic orientation w on G there is at least one
sink node, i.e., a node that has all its edges directed
to itself. Only sink nodes are allowed to operate
while other nodes remain idle. This obviously
ensures mutual exclusion at any access made to
shared resources by sink nodes. After operation
a sink node will reverse the orientation of all of
its edges, becoming a source and thus releasing
the access to resources to its neighbours. A new
acyclic orientation is defined and the whole process
is then repeated for the new set of sinks (Barbosa
& Gafni, 1989; Barbosa, 1996). Let w ' = g ( w )
denote this greedy operation. SER can be regarded
as the endless repetition of the application of g ( w )
upon G . Assuming that G is finite, it is easy to see
that eventually a set of acyclic orientations will be
repeated defining a period of length p . This simple
dynamics ensures that no deadlock or starvation
will ever occur since at every acyclic orientation
there is at least one sink, i.e., one node allowed
to operate. Also, it has been proven that inside
any period every node operates exactly m times
(Barbosa & Gafni, 1989), i.e., the value of m is
the same for all nodes within any period.
SER is a fully distributed algorithm of graph
dynamics. An interesting property of this algo-
rithm lies in its generality in the sense that any
topology will have its own set of possible SER
dynamics. Figure 1 illustrates the SER dynam-
ics.

According to the arguments of Collins (1995),
the traditional approach to modelling a locomo-
tor CPG has been to set up and analyse, either
analytically or numerically, the parameter-depen-
dent dynamics of a hypothesized neural circuit.
Motivated by Schöner et al.'s works, Collins
et al. dealed wth the CPGs dynamics from the
perspective of group theory (Collins & Stewart,
1993a,b). They considered various networks of
symmetrically coupled nonlinear oscillators and
examined how the symmetry of the respective
systems leads to a general class of phase-locked
oscillation patterns. In this approach the transi-
tions between different patterns can be modelled
as symmetry-breaking Hopf bifurcation. It is
well established that, in a Hopf bifurcation, the
dynamics of a nonlinear system may change when
its parameters are varied. An old limit cycle may
disappear and several new limit cycles may emerge
depending on how the model parameters change.
As the symmetries reach the least level, theoreti-
cally the chaotic phenomena may arise.
The theory of symmetric Hopf bifurcation
predicts that symmetric oscillator networks with
invariant structures can sustain multiple patterns
of rhythmic activities. It emphasizes that one in-
tact CPG architecture is sufficient for hosting all
possible pattern changes (Golubitsky et al., 1998).
This approach is significant in that it provides a
novel mechanism for generating gait transitions
in locomotor GPGs. The primary disadvantage
is that its model-independent feature makes it
difficult to provide information about the internal
dynamics of individual oscillators.