A Multi-level Planning and Navigation System for a Mobile Robot: A First Approach to HILARE

1. GENERAL DESCRIPTION AND PURPOSE OF HILARE

. ** The HILARE project started in Sept. 1977 as an attempt to provide the LAAS robotics group, as well as several other teams interested in that field in Toulouse, with a flexible and powerful experimental support for advanced research work on Robotics: a particular blend of Artificial Intelligence, Computer Science, Control Theory, and Instrumentation.

The choice of an autonomous mobile robot was made mainly for two reasons: 1) capacity to pro­ vide a variety of problems at different levels of generality and difficulty in a large domain - including perception, learning, decision-making, communication, etc., which all have to be consid­ ered within the-scope of ·the specific constraints of robotics: on-line computing, cost considera­ tions, operating ability and reliability; and 2) possibility to design a modular system which could be incrementally built and yet providing a t every step for interesting and useful research in many directions.

Research goals were programmed in these domains in accordance with the development of the system configuration. We emphasize that HILARE has no practical purpose in itself yet we are deeply concerned· in every stage of our work with methods and techniques, software and instrumentation for advanced applied robotics.

* Presently at LAAS; visiting researcher from the University of California, Berkeley, Calif. Visit made possible in part by ·the National Science Foundation Grant INT78-09263.

** Heuristiques Integrees au Logiciel et aux Automatismes dans un Robot Evolutif.

To date the system architecture (see Fig. 1) consists of (£f. /1/): 1) Perception: video cam­ era and laser range-finder mounted on a two-axes scanning system and integrated to provide fast rough scene analysis consistent with navigation needs; 2) Locomotion: one free front wheel and two motorized rear drive wheels; the microproc­ essor controlled step motors allow for a variety of speed and trajectory commands: straight lines, arcs with specified angular shift and rotation center; and 3) Computer System.

One of the more relevant characteristics which will aid advanced robotics with real-world con­ straints, such as cost-effectiveness, is an ap­ propriate computer system structure. Our organ­ ization (being investigated in several projects at LAAS) consists of 1) local distributed com­ puting facilities coordinated by a 16-bit MITRA 15 minicomputer, and 2) a remote time-shared IBM 370/168 system. Local facilities include onboard speciallized processing units (~., image preprocessing) together with 3 Intel 8085 micro­ computers. The MITRA 15 supports executive, de­ cision, and communication functions. The remote computer is programmed as a consultant system (see §2); it provides powerful resources in tasks such as learning, reprogramming, procedure opti­ mization, large data-base consulting, etc.

2. DISTRIBUTED DECISION-MAKING

In the system design of HILARE we have decided on a distributed decision-making capacity which al­ lows robustness, efficiency, economy of operation and timely system response. Our design can be viewed as decisions through multiple cooperating expert modules/5/ together with a high-level co­ ordinator in a hierarchical means-ends structure.

The expert modules have their expertise in a va­ riety of overlapping domains (~., object iden­ tification, navigation, exploration, itinerary planning). The modules consist of 1) special­ lized and redundant knowledge bases, 2) algo­ rithms and heuristics, 3) local error-processing capabilities, and 4) communication procedures. Modules may access one another as primitive action-units. The coordinator activates modules based on a means-ends analysis/2/ of the current situation.

2.1 High-Level Decision-Making and Planning

We are designing and programming a relational­ level planne·r at an advisor level. A plan at this level is a flexible dynamic structure which coordinates the achievement of desired goals/8/. Goal understanding includes 1) acknowledging or refusing an user order, 2) handling temporal and logical constraints, and 3) finding action-units which can achieve goals/7/. The planner must also include coordination of error processing, broadcast, and recovery procedures/9/.

Action-units may be primitive or macro actions (viz., entry-points into expert modules) /3/. The planner's required knowledge about actions includes limiting constraints and activation, continuation, and termination conditions.

Due to the incremental and open-ended nature of HILARE's design we consider Production Systems (PSs) a viable research tool for relational-level problem-solving. Thus, we are writing the plan­ ner in terms of a PS architecture in the spirit of /6/.

2. 2 Relational-Level World Model

The world model is contained in the PS data base: embedded non-recursive list structures which are associatively accessed by the pattern matcher during rule matching. The model is a hierarchy of object-centered concepts of the form

(name feature pattern-body)

which describe space and objects. Space is de­ fined by places (rooms, work-areas), frontier s (doors), and locations. Places have the proper­ ty of surface connexity and are connec ted t o other places by means of frontiers. Locations are elements within places which can be identi­ fied by point coordinates, relational descr i p­ tions, or feature descriptions.

Objects are defined by features(~., shape, color, and dimension) based on sensory percep­ tion. We define macro-objects by recurs i ve assembling and aggregation of objects.

3. NAVIGATION

In this section we consider the basic problem of moving a robot from an initial state (R) to the target (G) within a given place. This involves obstacle avoidance, path-finding, and search trajectory minimization/4,10/.

3.1 Navigation World Model

Currently, obstacles are defined as polyhedra, whose floor projections fully determine the nav­ igation problem, and they can be located either by initial information or by robot perception (see Fig. 2). Each obstacle projection is rep­ resented as an ordered list of segments in counter-clockwise sequence:~··

A segment is coded using the Cartesian coordi­ nates of its leftmost point(X,Y), its angle with a reference axis(.), and its length(r): S . {<X,Y>, ·· r}

Empty areas are defined as convex polygonal cells which include obstacle-seg;ents. A tra­ jectory within such cells can be considered as a straight line between entry and exit segments. In such cells ordering of segments Si is clockwise,~·· c1 {St, S~, ... , S§}.

Our partition algorithm which divides a known world into C-cells and obstacles is as follows. Starting at any vertex a C-cell is defined by following segments in a clockwise order as long as the angle between two successive segments is acute. When not, the algorithm jumps to the next visible segment,such that an acute angle is form­ ed and a convex cell is possible, and continues until a convex polygon is formed.

Any area including possibly unknown obstacles is defined as a polygonal *-cell, which is allowed­ ly non-convex,~·· C~ {Sf, S~, ·.· , Sf 5 }.

The topological properties of a place - divided into C-cells, *-cells, and obstacles - are graph r epresented. Two adjacent cells have connectiv­ ity through common segments which are travers­ able by the robot. Thus, a connectivity graph (see Fig. 3) provides the structure necessary for path finding.

3.2 Decision Procedure

The example in Fig. 2 produces among possible paths a single path between R and G which is com­ pletely determined since it does not include *- cells: c 1 (R) s~ c s~ c s~ C (G) In most --> 4 -+ 5 --> 6 · cases several paths would exist and a choice would be made through c-optimality concepts.

We define our cost function as: F = 1.:. (F! + F?); l l l i = ce ll index. F! measures every cost associat ed with det e rminea trajectory travel. To mini­ mize distance and energy requirements we have: F . =w1 d. + w2 I<P·I + w3n . , where for cell i 1) l l l l - d. is path length, 2) I<P · I is the angle of plann~d direc tion change, 3) 1 n. is the number of pre­ di c t ed r obot stops, and 4) 1 w. are weights. l

F? measures uncertainty and is evaluated over *­ c~ ll s: F? = w4d. (I*V - 1) , where I is a decreas­ ing posifive fufi c tion of the cell information which can be obtained by the robot at the entry segment : I = ST/S , and V measures path viability due to estimated obstacle clustering: V ~ 1/(1-T~ S is the maximal perceived area at the considered entry and ST is the total *-cell surface. T is the estimated ratio of aggregated obstacle sur­ face over the total *-cell surface (ST).

The minimization of F provides a method for path­ finding within a world which can be stepwise per­ ceptually identified by the robot.

In the case of partially known worlds cell con­ stuction is defined by the perceptual system as HILARE discovers its world. It may occur that non-traversable narrow cells are created; whereas another partitioning would allow traversal.

3.3 Object Close-Distance Navigation

Consistent with our viewpoint on multi-level de­ cision-making the problem of navigation can be resolved more efficiently with the introduction of a decision level which takes into considera­ tion a variety of navigation conditions which call for on-board closed-loop control, such as narrow corridor navigation, etc. This control is performed by HILARE using 10-close-range ultra­ sonic sensors regularly distributed over its surface. The higher decision levels including navigation set the objectives and the constraints for close-distance navigation with take-over and restitution of control locally defined.