Walking Robot: A Non-Deterministic Model Of Control

Introduction

There are two fields of study within the frames of the project.

1. The development of a mathematical model for the three upper levels of the control system for the robot's behaviour. This field is the principal one; however, it was agreed that the model should be testified in the conditions close enough to the real ones which brings about the necessity of the research in the other field.
2. The development of a computer system for simulating the robot's behavi­ our in complex topography.

The system of motion control

The control of motion for a walking robot is considered to be an interacting system of three principal levels:

Upper Level - the planning of route. This level is not connected directly with the specificity of "walking". In principle the problem here does not differ from the route planning for a wheeled robot. The only important factors for the control on this level are the general characteristics of the robot's capability to surmc~t ~i!­ ferent particular variants of relief.

Middle level - look-ahead for several trajectory steps in the direction of the route fixed by the upper level. Proceed­ ing from the complete information of the robot's capabilities the middle level takes into account all given values of output parameters of the motion regime (speed, balance reserve, the platform height etc.) and the local features of the relief in the direction of the aotion. In the space of all feasible positions of the robot on the relief this level of con­ trol points a "corridor" formed by the set of paths allowed under the given com­ bination and internal conditions.

Lower level - of control plans a eon­ crete sequence of elementary (for the gi­ ven level) acts of motion, the sequence is so chosen that the corresponding move­ ment through the area should keep to the "corridor" limits fixed by the middle le­ vel. The lower level chooses in What se­ quence the legs step on, fixes the points on the ground to put them, determines the moments of taking off and setting for each leg,the intervals for speed switching,eto.

It is understandable that even lower levels of control exist; e.g. the level which determines the concrete form of mo­ tion trajectories for legs and platform in accordance with the parameters specifi­ ed by the third level; and the level which realizes these trajectories (for a model allowing for different sorts of errors). These levels, however, will not be consi­ dered in the report because of the natural space limitations.

~

As the project is purely experimental in character, it has been decided to carry out the research for a sufficiently wide range of models with intention to shift the accent from simpler models to more complex ones (fig. 1a,b,c,d) as soon as a deeper understanding is felt.

Fig. 1b

Fig. 1c

Fig. 1d

The two simplest models are two - dimensional (plane). The legs have two degrees of freedom each, they can move in the plane of movement Wl.thout being caught in each other or in the platfom (they can intersect). The remaining two models are three-dimensional the legs having three degrees of freedom each. All four versions are considered to have no mass but they have a center of gravity (legs are weightless).

The following restrictions are im­ posed on any model:

1. The static balance condition:the vertical projection of the gravity center must cross the supporting segment for the 2-D models and the supporting polygon for the .3-D models.·
2. The bearing (of a bearing leg) cannot move along the relief, i.e. the robot is not allowed to "drag its legs".
3. (.3) Every step, i.e. the operations of taking off, transferring and setting a leg, requires an interval ~+ t of time, where 'l:0 is a constant and t is chosen by the model randomly within the limits of restrictions (1) and (2).

Generator of Behaviour

For each model a set of variables is fixed which completely describes its inner state. For example, the variables for the simplest model (see fig. 1a) are fixed as follows:

• coordinates of the bearing with respect to the gravity center,
• the time which has passed since non-bearing legs took off,
• vertical and horizontal velocity constituents of the gravity center.

Statically unstable states are ex­ cluded from all possible sets of variable values. Each model is specified by a coup­ le of (Q,A) , where Q is the set of all statically stable states and A is the set of simple operations managed by the model. For instance, 1a model manages the follow­ ing simple operations:

· The convex figure (reduced to a segment for the 2~D models), formed by a round of projections of leg bearing onto a ho­ rizontal plane, is referred to as t~~ supporting one.

• status quo-maintaining the current values for the two velocity consti­ tuents,
• taking ott a bearing leg,
• altering one of the constituents values by ±. 1 ,
• setting the taken-off leg into the point of given relative coordinates.

Any set of simple operations that can be applied simultaneously forms a com­ plex operation. Let I be the set of all operations- simple and complex ones-defin­ ed by A; generally, when a simple or com­ plex operation is applied, the model pas­ ses into a ne%t state which, in its turn, may or may not belong to the set Q.

Thus, for any model a corresponding oriented graph G may be constructed whose vertices are the states of the set Q and the a£CS are the respective operations from A. The set Q'is now naturally divid­ ed into three non-intersecting subsets:

• cyclic states which belong to at least one cycle from G;
• input conditions which have at least one path into cyclic ones;
• deadlock states.

The subgraph obtained by excluding the deadlock vertices from G is callea the generator of behaviour.

We oan next select subgenerators from the generator of behaviour which sa­ tisfy certain restrictions imposed on choosing the states from Q. There is, for instance, a subgenerator with a given lOW"­ er or upper limit of the velocity range or a given minimum of balance reserve! a subgenerator of motion on a horizonta plane, etc. To meet this, vertices are selected in the generator which satisfy relevant restrictions, deadlock vertices are excluded from the subgraph obtained.

Let the model (Q,A) be in a given point of the relief with its inner state q· E Q, any sequence of the robot' a ac­ tions for this initial position defines a corresponding sequence of the inner states q·, q', q",··· , efch couple of the adjacent states ql, q ·~ as~~ the realization of an operation aEA/u(qf) · =qL+4 · Any sequence of the model's actions on the relief is re-affirmed by at least one path in the behaviour generator. All paths beginning in a given q· in G may be divided into two paths - with the position on the relief fixed - 1) those correspond­ ing to a sequence of actions, "feasible" on the relief and 2) those, "infeasible" on the relief. We can next select paths from all "feasible" ones that satisfy cer­ tain restriction imposed on the choice of states; it is evident that the set of s~ch paths is the same as the set of ~11 ~taus­ ible" paths in the corresponding subgene­ rator.

We shall select paths from the set of all "feasible" paths going through q* in Q which correspond to the robot ·s mo­ tion on the relief in the direction to some goal or sub-goal, specified by a su­ perior level. This set of paths "satisfy­ ing the leading directions" forms the ·be­ haviour corridor" which containst in its turn, "narrower" behaviour oorriCI.ors sat­ isfying different restrictions imposed on the choice of state.

General scheme of oontrol

Let us return to the general scheme of the model control. A set ot control parameters is chosen whose values are sp&­ oified from outside (by even higher con­ trol levels or by a human o~erator), e.g. velocity, balance, comfort {limitat1ons imposed on the manoeuvre by velocity and the movement ot the platform), et~.

Up;jr level' parameter values essen­ tially feet the estimation ot relief and, respectivelyt the choice of route by the upper level or control. Two versions of this level are effected in the project:

1. Statio version. Right from the start the robot disposes of a detailed plan of the territory,it knows its coor­ dinates and the coordinates ot the goal. The problem of routing is completely solv­ ed before the movement begins. The terri­ tory plan is divided into homogeneous are­ as similar as to their practicability fac­ tors, i.e. slope, height, surface condi­ tions (screen, marsh, etc.). The values of control parameters considered, these areas are given a concrete estimation upon which an optimal route is determined with the help of the well-known methods (algo­ rithms of Bellman [3], Nilssen [4]).This version, as can be seen, means that the upper level does not work during the mo­ tion along the route.
2. D~amic version. The robot's knowledge o the territory compr:!.:::::~ only what it sees and what it has seen since the motion began. In addition the robot knows its own coordinates and the coordi­ nates of the goal. "Functions of the eye" are not simulated; the robot is supposed to have "ideal eyes". For any given posi­ tion on the territory, a zone of direct vision is determined, the corresponding part of the plan is considered as known to and memorized by the robot. The discus­ sed operations of dividing into areas and practicability estimation are carried out for the known portion of the plan. There upon the tactics of movement are determin­ ed and the following stage of route is marked out. The statio version is now com­ pletely realized; as for the dynamic ver­ sion, a tentative model is at ine aebug­ ging stage.

Middle level marks out the wvtiv~ corridor for several steps ahead. Only the principal relief components are taken into account; minor relief elements are supposed to be treated by the lower level using the manoeuvrability wtthin the cor­ ridor.

The fixed values of control parame­ ters determine a corresponding subgenera­ tor of behaviour for which the corridor is constructed. If construction proves im­ possible the value range is extended for certain parameters (provided it is permis­ sible); this enables the use of a more ex­ tended subgenerator. When the corridor is marked out for an acceptable set of the parameter values, the control passes to the lower level; it, on the other hand, the try did not succeed, the "conflict" is reported to the upper level since it has been caused by an error of the latter.

Lower level: the set of values of the parameters for Which the corridor has been marked out determines the subgenerator of the lower level. When inside the corridor, the lower level is .able to control the mo­ tion taking into account the details of relief for the nearest step only, i.e.the robot is walking "looking at its feet".

It operates as follows: any point of setting of the next leg is selected inside the corridor, the level chooses a path in the subgenerator (optimal or quazi-opti­ mal); this path has to be permissible for the relief and to lead from the current state to any other state in the corridor corresponding to the setting of the given leg into the given point and allowed by the corridor; after that a decision is made as to which leg will step next, the point of setting is planned for this leg, etc.

We have now a working 1a model for a black- and-white ·plane relief (black­ no treating, white - treating allowed). The development is being completed for 1a model on an arbitrarily complex (flat) re­ lief; as well as for 1b model and black - and - white relief. Certain results are obtained in methods ot automatic synthesis and compact computer presentation for the generator of behaviour.

The simulation system

In this preprint we shall only enu­ merate some of the most general functions of the simulation system. The system con­ sists of two principal parts.

1. A dialogue system for synthesis of complex relief. The system uses a dis­ play and a plotter. The system constructs a two or three - level model of a complex relief "on demand", using only a minimum of directions from the operator.
2. The operation system, wh.ic~ ena­ bles:

1. real time interaction of the th!'!'e control levels;
2. interaction between the robot's model (lower control levels and the block of visualization) and the system of control;
3. interaction of the robot's model and the relief model; visualiza­ tion of the simulation process on the display.