11 
je 
al 
1t 
Finat, Javier 
  
  
Anyway, there are well-known algorithms for transference and fine motions, which operate following a decision tree for 
each open kinematic chain: one starts by introducing a material point (Cc; by example), one constructs feasible trajectories 
compatible with mechanical constraints, one simulates the behavior of solutions and one optimizes the resulting solutions 
according to metric, probabilistic or smoothing criteria. This approach is based on the mechanical behavior of a material 
point (the center of gravity, e.g.) and the construction of a tubular neighborhood for feasible trajectories where the 
optimization and control is performed. So, the incorporation of additional constraints follows hierarchised scheme which 
makes easier the updating of the information process in changing environments. To avoid an expensive maintainance in 
odometric terms ones uses the lines geometry: it incorporates incidence conditions which are computationally translated 
in doubly connected lists. 
4 AMODEL-BASED APPROACH FOR THE ALGORITHMS DESIGN 
Following our hierarchised approach, the algorithms design for locomotion planning can be formulated w.r.t. the articular 
or configuration C or the working space W. Both spaces are linked by the natural projection 7 : C — WV, and their 
k-th order prolongations (see the EMAD, below). The local geometry of the global situation presents a lot of pathologies 
(singularities, e.g.), and it is convenient to adopt a simplified representation obtained by overimposing onto the working 
space a general hierarchised combinatorial geometric structure (supported onto flag manifolds) for a changing mechan- 
ics, motion planning and an adaptive control of articulated mechanisms in locomotion tasks. The tangent space to this 
hierarchised system provides enough vector fields to support any exchange between different modules. 
Failures between current and desired dynamical data of the certificates associated to the control points or lines can appear 
along the updating process. It is necessary to prevent and correct these discrepancies in terms of a queue of internal events. 
The most important problem concerns to the feedback between different levels (geometry, kinematics and dynamics) of 
mechanics. To this goal, the use of the lines geometry for the support allow us to avoid the odometry problems (the 
calibration can be restated in these terms, but it will not be considered here by space reasons). Next, one introduces 
the simplest scheme based on ordinary small rotations in C and one propagates along the mechanism. The difficult 
question concerns to optimize the sequencing rotation at joints along each kinematic chain of the multibody for a better 
performance of motion. This is achieved by using symmetric temporal patterns of the dynamical models with hierarchised 
control systems (symmetries are generated by reflections); a SVD for the pseudo-inverse matrix associated to several 
simultaneous rotations allow us to optimize the right distribution of impulses. 
4.1 Algorithms and constraints for the Geometry 
The geometric aspects of algorithms design depend on the architecture and the scene. Their goal is to determine the 
reachability region for each component in terms of the maximal elongation of legs (Delaunay triangulations ). If all the 
joints are rotational, this constraint is computed by differentiation of the length constant conditions for each component; 
the coupling for each leg is performed onto a three-dimensional torus T? — S! x S! x S!, where each S! corresponds 
to a rotational joint. The resulting values for each component are patched together and this gives a planar representation 
in terms of intersecting circles, to characterize feasible equilibrium postures; to do that one uses lists of certificates which 
evaluate and correct the errors arising from small differences between desired and current position-orientation by using 
polar coordinates for each rotational joint. 
The new aspect concerns now to the feasibility provides effective criteria to describe an average between singular or 
exceptional configurations for each leg (characterized by 0; — k for each rotational joint, e.g.), and admissible values 
to avoid self-collision between different legs based on allowable circles to be simulated by each leg before starting the 
motion. The influence region of each leg for each phase in the aerial navigation phase is computed from a mobile planar 
Voronoi diagram in the working space associated to six mobile points corresponding to the orthogonal projection onto the 
motion plane of the ends of legs. 
In fact we must look only at most three mobile points in swing phase: a) in the biped case we have two triples of aligned 
points given by the (projections of) of hip, knee and ankle as control nodes for each leg, which gives degenerate Voronoi 
diagrams (by the alignment of control nodes); b) for more stable static machines s.t. hexapod robots one has a similar 
reasoning, but by replacing the above control nodes by the ends of each leg. 
The convexity constraints for influence or Voronoi regions allow us to apply standard optimization criteria. All these 
constraints determine optimal equilibrium configurations for the polygonal support (tripod gait at least for multilegged 
robots) associated to the dual Delaunay triangulation. By using the maps appearing into the EMAD, it is possible to 
transfer this information to the working space with corresponding constraints g; in addition, the existence of local sections, 
allows us to lift this information to the kinematics and dynamic framework, and to evaluate the coherence with additional 
constraints of higher level. 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B5. Amsterdam 2000. 243