Planning The Activity Of Robot With Artificial Intelligence

PLANNING THE ACTIVITY OF ROBOT WITH ARTIFICIAL

INTELLIGENCE

E.S. Kuzin, G.E. Pozdnyak and I.B.Fominykh

The Institute of Normal Physiology, USSR, Moscow

!batract

The paper deals with a number of problems involved in planning a robot's activity. A formalized statement of the planning problem is proposed and the theoretical principles of design and re­ quirements to structure of the problem environment models and planning algo­ rithms are discussed. A problem environ­ ment model is conceived as a set of in­ terrelated data on the real world of a robot's functioning that are necessary and sufficient for the solution of all problema belonging to a certain class. Algorithm is understood as a generalized procedure defined on a problem environ­ ment model.

Let us consider the functioning of a certain class of artificial systems performing actions in a three-dimensional space. We shall introduce the notion of the working space of a system, conceiving it as the space which is physically accessible to the system for performing the actions it commits. Then by robots we shall understand a class of function­ ally similar automata having a memory and intended for executing directed chan­ ges of the properties of the components of environment or relations between these within their working space by means of manipulations with tools and (or)objects. We presume the existence of potential feasibility of manipulating according to

any spacial law.

The simplest robots are devices functioning on the basis of a rigid pro­

gram. Programs are supplied to the robot to be subsequently implemented in the form of certain influences on the envi­ ronment in a sequence which is in advance defined by man (in the general case by a metasystem, i.e. system having a higher level of control as compared with the ro­ bot). Moreover in some cases the choice of actions of the robot may be addition­ ally controlled by changes of its phys­ ical state and resource capacity. The further sophistication of the robots ac­ companied by an increase of their auto­ nomy necessitates incorporating in their control systems such mechanisms as affo!d during the choice of action automatical­ ly to take account of situations arising in the robot's working space (and in more developed systems also situations embra­ cing the entire problem environment of the robot is a pre-trained system clas­ sifying situations arising in the envi­ ronment and choosing the a priori stated action sequences that are adequate to these sitUations. However, in complex en­ vironments involving a great number of components which affect the robot's act­ ivity, an a priori classification of situation· may prove practically impos­ sible. In this ease the robot must be able to form independently the sequence of actions that would be adequate to any situation arising in the problem environ­ ment, i.e. it must be able to solve the planning problem. The control system of the robot must in this case be potential­ ly prepared for executing a great set of actions in perception control of movement of executive organs, decision making and dialogue with the metasystem.

In posing tasks for the robot and correcting its activity by way of dialogue the metasystem proceeds from percep­ tion on analysis of a far wider problem environment than is accessible for the robot. In this sense the more perfect robots should be endowed with the capa­ city of an interlocutor with the metasys­ tem or an active observer of some of the components of its problem situation so as to take part in the metasystem's task setting process and sometimes automatic­ ally to perform such an adjustment of tasks set before the robot by the meta­ system as would be desirable for the lat­ ter in taking account of the metasystem's problem situation.

One can visualize a system having "maximum" potentiality in this sense as a certain idealized autonomous robot which, being capable of adaptation and learning, could be able in any situation independently to form models of the re­ sults expected of it by the metasystem in ~eeping with its functional purpose and efficaciously to achieve these re­ sults.

Efficient solution of the planning problem is a key aspect in the activity of any autonomous robot having a suffi­ ciently high level of development. A more detailed analysis of this problem is the subject of the following discussion.

Planning is understood as the task for the robot automatically to form a se­ quence of actions (by means of which it can influence the environment) as well as such corresponding subgoals achieved by fulfillment of these actions as would lead to the required goal.

To provide for the planning process, it is necessary to enter into the robot, before it begins to function, a model of the problem environment (henceforward,PE model) and algorithm-like information (henceforward,planning algorithm) reflec­ ting the logic and information processing rules specified in the form of the PE mo­ del. In the general case the PE model or fragments thereof may be formed and entered either by human operator or auto­ matically with the aid of learning mecha nism during preliminary simulation of t robot's possible activity · .

The model of problem environment is a totality of interrelated data about th real world where the robot is function­ ing which are necessary and sufficient for solving a majority of problems of a certain class. (The problem class is de­ termined by the designers according to the robot's purpose). Since the PE model ia developed for the solution of a cer­ tain class of problems, information it contains should be problem oriented in the framework of that class. However, in the general case it does not seem pos­ sible to take into account in a PE model all data that are necessary and suffici­ ent for solving all problems of a given class. Furthermore,since robot's activ­ ity takes place in a real environment, information reflected in the PE model is of a limited accuracy. Therefore in real cases one should reckon with the fact that PE model is incomplete and inaccur­ ate.

Information contained in the PE mo­ del includes both data of a general na­ ture that are valid for the entire prob­ lem class as well as special information valid solely for a given particular prob lem of the class.

The information of the former kind includes:

• data on the regularities of the real environment, i.e. data on environment components, ties and relationships ex­ isting between these components;
• data on the possible influences upon the environment on the part of the ro­ bot (actions) and the changes these cause;
• data on the possible changes in the e vironment independent of the robot;
• data on the robot itself and on its pot en tiali t.i,es.

Information of the second kind which characterizes the conditions for the solution of a particular problem in­ cludes:

• data on the environment components which are concerned by the particular problem posed;
• data on the required solution result;
• data on restrictions imposed on the process of solution of the problem under consideration.

The major difficulties to be sur­ mounted in solving the planning problem spring from the necessity of efficient r· presentation of information about the real world in the framework of a certain formal system (in other worlds from the choice or development of a suitable lan­ guage for the description of the problem environment) and also from the necessity of elaborating algorithms adequate to this representation and implemented in the same formal system. One such system is described below using the notions of set theory.

For description of the environment, abstract finite sets R, n ,B ,S, are in­ troduced which may be respectively inter­ preted as mapping, 1n the problem envi­ ronment model, of the set of relations, qharacteristics, objects and situations existing in the real environment. For simplicity's sake, the terms situation, relations, etc. will be henceforward re­ ferred directly to problem environment model without additional stipulation. Each feature n, c n may assume a cer1ain finite set of values {:Iii i ' ] which is either a subset of real numbers or an or­ dered set whose elements are qualitative c;- . . descriptions. Among the elements of :/Ji /' there can exist the element ~ which de­ signate the absence of a characteristic.

Within the framework of the formal system the concept of structure is in­ troduc.ed. The simplest structure is a triplet x ; 1..: Xi which may be interpreted as a proposition. The other types of structure can be represented as a set of triplets { :x. , 't.l{ Ij ~

where .X.;,:rj are the elements of the set of relations,characterist­ ics,characteristic values, objects,situations and other categories introduced for representation of PE model

and 't" are the elements of the set of relations.

Then the object Bd E B may be represen­ ted in two fashions:

object being sought for. (In substantial terms this corresponds to representing the object through its relations with other objects or as the set of charac­ teristic values).

- or as a set of triplets of the type

(In substantial terms this corresponds to a certain structure to which the name of a given object Cj· is ascribed).

Situation is understood as descrip­ tion of a certain situation in the en­ vironment taking shape under certain con­ ditions. Presumably it is permitted to consider as the problem environment not only situations obtaining by fixing a certain time point but also situations due to fixation of other environment pa­ rameters. Examples of these are situatiao of hunger, thirst etc.

At the formal level, the situation S«cS may be represented as the set of triplets

The action ~· € U is introduced as the

in which substructures are distinguished that characterize the conditions of app­ licability of the given action, the con­ sequences of its application and the pa­ rameters liable to change. In the struc­ ture of the action the objects to which it may be applied are also specified.

Actions may be aimed at transforma­ tion of the environment or at its explo­ ratioa (in particular, actions involved in perception of environment). In the latter case the result of application o! the action will be a change not o! a real environment but of the notion the robot baa about it. The presence of the latter category of actions is justified by two reasons. First, for autonomous function­ ing o! an integrated robot current infor­ mation about the environment must be ob­ tained directly from the perceiving sys­ tem. In a broader sense, robot's activity in exploring the environment regularities is due to the need of a periodic correc­ tion and updating of the PE model.

A rational organization of the plan­ ning process calls for a hierarchical or­ ganization of actions: from simple (ele­ aentary) up to composite (generalized)ac­ tions of various levels.Simple actions 1A this case are conceived as those which within the framework of a given PE model are not representable (in contrast to coaposite actions) aa sequences of more elementary ones.

The possible changes of environment independent of the robot may be incor­ porated by introducing input influences 9i € G defined by means of the mapping formula

chastic or deterministic j;. :..is sto­ function.

The description of various environ­ ment components and relations between them, description of robot's actions and

influences independent of it aa well as the description of the components of the environment in relations to which the particular task is posed constitute the initial model of the problem environment for a given task, which is henceforward denoted as Mo · It should be emphasized that all components of the PE model are closely interrelated and expressed (ex­ plained) in terms of one another,constit­ uting jointly with the planning algorithm an integrated system of knowledge.

The goal set before the robot by certain metasystem (in a majority of cases, human operator) in the general case is to achieve a certain situation in the environment, which will be hence­ forward referred to as the goal situati~ In non-trivial problem environments the goal situation S:z c:- S is usually multi­ component and such that the determination of its various components ia of an un­ equal importance. Accordingly, at the formal level the result is introduced aa

a set of weighted goal si tuation· sl c s .

the weights may be determined with the aid of the goal function f :

where s~ c S.

However, in complex problem environments an exact analytical (or tabular) speci­ fication of the goal functions may proTe to be difficult. In these cases the pre­ ference scale of indiTidual subsets of the set of goal situations ~l need not always specify clearcut boundaries of the variation of its Talues. That is,goal situations may be estimated using such vague notions as "desirable","necassary" etc.

Over and above goal situations, it is possible to define the set the un­ favourable situations SH that the robot seeks to avoid, introducin! to estimate

them the functions h :

where SH is the set of unfavourable si­ tuations, !111 c S

In expressions (6), (7): F ,H- are subsets of real numbers or ordered sets whose elements are qualitative descrip­ tions. With respect to the function h the same stipulation is valid as concerns the goal functionj6 · On the basis of the PE model and the planning algorithm the planning system must draw up a plan for the accomplishment of a particular taak, i.e. it must state such a sequence of actions and their correspondent cur­ rent goal situations which would lead to the result required by the given task. Or, in more exact terms, specified for the robot's planning system are:

• initial environment model Mo;
• finite set of goal situations and unfavourable situations SJ, SH;
• estimator functions f , h i
• algorithm-like information (planning algori tbm).

The system is required to build a plan li which would maximize the fol­ lowing functional:

In the general case a plan is understood as an ordered set of duplets:

rfi

j i

/r1 -I( I . .

where Mo is the initial environment mo­ del; s:' m, s;i

i.

i

i

U, t1 m-t lim -lot t/.,

I

)

J

• subplans corresponding to composite ac­
• tions.

In relations (9), (10):

- current goal

situations,

- simple actions.

are simple actions and current goal situations corresponding to the " subplan ~·

are simple actions and current goal situations corresponding to the A subplan !.c ·

It is appropriate to note here that the planning process in a sufficiently comp­ lex problem environment may be practical­ ly (and all the more eo, efficaciously) executed only provided it has a multi­ level and hierarchical character. That is to say, at the generalized (composite) actions of the highest level should be found that would enable achievement of these subgoals. At the next level more detailed subgoals are specified etc. The planning process ends when the whole se­ quence of actions constituting the plan is composed of elementary actions alone. In relation (9) only two planning levels are represented for the sake or simpli­ city.

We shall now consider some princip­ les of design and requirements to the structure of problem environment models and planning algorithms.

A prime requirement to PE model structure is that it should be build in keeping with the principle of generaliz­ ation and aggregation (otherwise, given a high diversity of data, the model could become unmanageable). Generaliza­ tion is in these cases understood as building the generic relationships bet­ ween concepts, and aggregation, as ascr~ ing names to certain structures.

Aggregations and generalizations like the whole of PE model in the general case, may be formed either automatically by learning mechanisms or with partici­ pation of man on the basis of a priori analysis of the class of problems that the robot will have to solve. However, even in the latter case, over and above invormation introduced a priori, the PE model due to its incompleteness and in­ accuracy must be updated and adjusted by information obtained both during the planning process and during the func­ tioning of the robot in the real environ­ ment. This process, too, may be either automatic or performed by man interact­ ing with the robot through a dialogue system.

It is admissible that information represented in PE model may be at in­ dividual stages of system functioning redundant and moreover contradictory. The contradictory character reflects the insufficiency and inaccuracy of the know­ ledge about an object or phenomenon as possessed by the robot and it may work as stimulus for further exploration of the environment. By redundancy we mean the possibility for deriving one and the same information from various statements about a certain object or phenomenon that are comprised in the PE model. Re­ dundancy is typical of a great many prob­ lem environments that are to some extent untrivial, especially if models of these environments are formed automatically during robot's functioning in the real environment.

In contrast to PE model where in­ formation is predominantly assortive, knowledge in the planning algorithm is expressed only in the imperative. In other words, the planning algorithm is a generalized procedure or, more exactly, a set of procedures defined on the PE model. This procedure must be built as universal at least within the scope of a certain class of tasks to be decided by the robot and possibly within the scope of a family of classes. The latter means that the algorithm must produce a correct solution independent of the conditions of a particular task of a given class.

It is appropriate to note here that the division of information into know­ ledge containing the PE model and the knowledge expressed as algorithm is nominal and again to emphasize the in­ tegrated character of the entire system of knowledge possessed by the robot. Indeed one and the same information may be specified either in the form of pre­ stated facts (and incorporated in the PE model) or obtained by way of a cer­ tain procedure (included in the algo­ rithm). Besides, the procedures included in the planning algorithm may be de­ scribed similarly to actions and in­ cluded in the PE model. The point is to provide such relationship between facts and procedures as would enable the sys­ tem efficiently to perform the planning function.

The planning procedure must provide for a purpose-oriented activity of the robot. Stimuli for such activity are a mismatch between the result required by a particular task and the initial envi­ ronment model and detection of uncertain­ ties during comparison of the goal si­ tuations with the initial environment model. Uncertainties are all those cases which necessitate additional exploration of the problem environment by the robot. The robot may accomplish this process by means of its own perceptor system, fail­ ing to do this, it must have the possib­ ility of referring for explanation to the metasystem (human operator). In the latter case metasystem - robot interac­ tion should be organized by means of a dialogue system.

A mismatch may be a difference in the values of characteristics, rela­ tions, etc. In the formal language adop­ ted, the mismatches by characteristic values are determined by the conditions (12): if the propositions .Zi'Zc.Ij E Si. and the proposi tiona .Zm 7: t :Xn E /'1 0 then the mismatch is fixed, provided that

where

.:Xi E- 8k'

.Zm E B~

~· c {.7iJj, Xn E {fii'J,

I

,

'(KE: R tt E R

'

J

'

B.< - is

a subset of the object set B , and [ ..Jii lj - is the set of values of the characteristic ni .

The mismatches of relations are deter­ mined by the conditions (13):

where Rt is a subset of the set R and X i , .Xm, .Xi, X"- are elements of the set B ·

The solution of the planning prob­ lem can be presented as a sequence of cycles, in each of which the action (simple or composite) is sought that eli­ minates (or reduces) this or that mis­ match or uncertainty but in the general case requires, as a condition for ita application, a new situation, which, in turn, appears as the current goal at the next planning cycle. The efficacy of this process largely depends on the choice of the current mismatch (or un­ certainty) and the its eliminating act­ ion; this choice may be conveniently based on checking upon the applicability conditions of each "candidate" action and assessing the consequences of its application. The ultimate plan should be chosen on the basis of a criterion con­ nected with the main functional (see re­ lations (8)). By way of such a criterion it is possible to use, for example, the requirements of minimum time and power spent on problem solution.

We should like to note on conclusion that the planning problem as stated above may occur in various subsystems of an integrated robot: the perceptor system, the effector system, and the central sy~ tem. For instance, the planning in the perceptor system may be elaborating a sequence of operators affording, say,to identify some body or establish rela­ tions between certain objects existing in a given scene.

The planning in a manipulator con­ trol system or locomotion control system may involve elaborating a particular trajectory of the movement of the "hand· or the carriage. In relation to the plan­ ning performed in the central control system (CCS), the planning in other sub­ systems is of a local and subordinate character in the sense that the goals of each local planning are formed in the robot's CCS and transmitted to its sub­ systems. Consequently, similarly to the hierarchy of integrated robot's subsys­ tem, one should speak also about the hierarchy of the planning problems arising in these subsystems.