Model Structuring and Concept Recognition: Two Aspects of Learning for a Mobile Robot

1. INTRODUCTION

This paper presents two aspects of learning : concept Learning and procedure learning by genera­ lization. It deals specifically with navigation and locomotion problems for a mobile robot. Actual prac­ tical applications for such a robot are for example: night-watchman (patroling and anomaly detecting in a known environment) robot- cleaner, robot­ conveyor, waiter .··

The experimental support for our system is HILARE*, a mobile robot. A navigation procedure ba­ sed on an initial level of modelling of the universe has been defined by R. Chati La /1/. Our approach uses his work which is summarized in part 1. The initial model is a graph. ·we shall see the motives (part 3) which have led us to the structuring of this model by a decomposition of the graph into con­ nectivity components (part 4). The tools, some of them original, come from graph theory. We shall define a new itinerary procedure as being a generali­ zationof the navigation procedure (part 5). Sub­ graph labelling of the decomposition leads to con­ cept learning (part 6) ; its implications in the improvement of man-robot communication will be dealt with. Finally, in part 7, in a more prospec­ tive way, we shall tackle the problem of area re­ cognition by subgraph isomorphism.

2. HILARE. UNIVERSE MODELLING. NAVIGATION

As far as learning is concerned, we shall limit our presentation of HILARE to decision-making, uni­ verse modelling and navigation.

1. Hilare's decision-making consists of :
2. multiple independant modules (vision, locomotion, navigation, object identification, ··· ) which are used to build a plan, and

*"Heuristiques Integrees au Logi ciel et aux Automa­ tismes dans un Robot Evolutif". HILARE is also used as an experimental support for the learning of de­ cision rules in plan generation.

• a coordinator superv1s1ng the development and execution of the plan /2- 3/.

As yet, this system is not entirely defined and is a current research topic. It may be progressively enriched by adding new modules. The integration of learning capabilities for each module can thus be taken into account. It is the case for the itinerary.

2.2. Universe modelling : HILARE move; in a closed space of rooms cluttered with objects a priori con­ sidered as obstacles and whose geometrical projec­ tion on the locomotion plane is modclled by polygons. This set of polygons, together with the "floor plan" of the rooms leads to a initial geometrical model.

The navigation space is then partitionned into convex cells free of obstacles in which any two point~ can be linked by a straight line (Fig.1). This leads to a planar graph * representation : nodes correspond to cells and edges to common frontier-segments for adjacent cells (Fig.2). This model is topological ; e~ery single face** characte­ rizes an obstacle. Notice that the graph representa­ tion is easily extended as new rooms are explored.

1. The navigation procedure allows the research for a trajectory between two points S1 and S2 to be transformed into a path search in a graph by the following procedure :
2. Find the cells C1 and C2 which contain S1 and S2 (1 and 5 in Fig.1).
3. Search a path T between C1 and C2 in the cell graph (1-2-3-10-9-5 in Fig.2).
4. Find the corresponding geometrical path G formed with the middle of the frontier-segment between the cells in T (dotted line in Fig.D.
5. The trajectory is obtained by smoothing G.

The most important part of the procedure (the determination of the trajectory draft) is made in stage 2, by an admissible heuristic search which includes cell metrics. Learning improves this search.

3. MOTIVATIONS

If in order to go from a point S1 (contained in a cell C1) to a point S2 (contained in a cell C2) of the navigation space (of the cell graph), the robot must go through a door (cell A), the problem of finding a trajectory (path search) may be decom­ posed into : find a path from S1 (C1) to the door (A) and a path from the door (A) to S2 (C2). In the graph representation A is an articulation node ;,those removal will disconnect the graph. Hence the graph decomposition into connectivity components will enable us to decompose and simplify the navi­ gation procedure.

A planar graph has a representation in the plan such that two edges intersect in a node. **A face is a cycle in which a defined area of the PLan contains no nodes.

Moreover, when we consider Fig.1, in order to go from any point in the room R2 to any point in the room R4, we must go through room R3 ; it would be much better to memorize definitively the path wi­ thin room R3.

Finally, area concept learning is necessary in order to build a man-robot communication language close to natural language (see /4/). The graph decomposition can be analysed with a view to this aim.

4. DECOMPOSITION OF THE GRAPH

By definition, a graph with at least k+2 nodes is k-connected iff it is still connected after the withdrawal of k-1 nodes (or equivalently iff there exist ateast k distinct paths between any-pair of nodes ) . An articulation set is a node set whose.withdrawalleads to an unconnected graph. The decomposition is the search of k-connected subgraphs. We shall deal only with the cases k=2 and k=3. The chosen method is specific to planar graphs. The in­ put data of the algorithm are the faces of the graph ; easily obtained from the geometrical model by following around the sides of obstacles. These data lead to simpler algorithms than the classical ones /5/. Decomposition up to the triconnectivity level is based on the characterisation of arti cula­ tion nodes and pairs, established in /6- 71 : -A node is an articulation node~ it appears twice in a face.

- A node pair is an articulation pair iff it appears in two faces (or three faces if this palr is an edge).

The decomposition algorithm into biconnected com­ ponents* goes over every face in the graph. When an articulation node appears, it partitions the face. The partition elements are the bases of the bicon­ nected components. In the example of Fig.2, the external face gives the partition 1-2-3-4, 3-10-911-14-20-19-17-16-15, 9-5, S-6-8-7, 19-24, 24-25, and 25-23-22-26 with the nodes 3,9,5,19,24,25 as articulation nodes (see /6/ for details).

For the decomposition into triconnected compo­ nents**, we propose in /6/ a quadratic algorithm which finds all articulation pairs. It compares favorably to the linear algorithm developed by Hopcroft and Tarjan /5/ for planar graphs with up to 300 nodes and 800 edges.

The set of articulation nodes, articulation pairs, biconnected and triconnected components can be structured into a tree /8/. Two nodes representing triconnected components are adjacent if they con­ tain the same articulation pair; two subtrees re­ presenting biconnected components are adjacent if they contain the same articulation node.

Fig.3 represents the decomposition tree of the graph in Fig.2 (up to biconnected components).

5. ITINERARY PROCEDURE

Th1s procedure generalizes the navigation proce­ dure ; it decomposes the path-search problem into subproblems which are almost all solved by an ini­ tial processing.

* The biconnected components are biconnected. sub~raphs or edges.

*The triconnected components are triconnected sub­ graphs or elementary cycles.

5.1. Preprocessing : it memorizes the path between the nodes of separation sets belonging to the same component. These paths are found by the navi­ gation procedure. Fig.3 shows an example of a memo­ rized path.

1. Itinerary : the decomposition structure and the prememorization having been defined, the search of a path between two points S1 and S2 by the itine­ rary procedure is done as follows :
2. 1.Find the cells C1 and C2 containing S1 and S2. 2.Find the components K1 and K2 of decomposition tree tree containing C1 and C2.
3. 1-If K1=K2, return the path given by the naviga­ tion procedure used only in K1
4. 2-Else 1.Find the path between K1 and K2 in the tree (K1-K4-K2 in Fig. 3)
5. 2.Fetch the corresponding prememorized path P.
6. 3.Find the path P1 between C1 and the first node of P, using the navigation procedure in K1, and the path P2 between the last node 6f P and C2, using the na­ vigation procedure in K2.
7. 4.Return the path P1 U P U P2.

The complete set of algorithms mentioned here (navigation, planar graph decomposition, preproces­ sing, itinerary) have been implemented in APL.

5.3. Complexity : the use of the navigation procedu­ re in the steps 3-1 or 3-2-3 gives its complexity to the itinerary procedure. The step 3-2-1 is linear. Therein lies the originality of the itinerary modu­ le : it transforms the path search in a GRAPH into a path search in a TREE. The preprocessing complexity is also determined by the navigation procedure tor the path prememorization. Graph decomposition is linear. According to our experiments, the cost of the preprocessing is paid off by a few robot moves .. In a more complex example than the one pre­ sented here (57 cells), 12 calls to the itinerary procedure were sufficient in the average.

5.4. Note : as a matter of fact, the prememorization cannot take into account the advent of unexpected obstacles during room traversal. This kind of event is specifically processed by the supervising coordi­ nator (cf.§ 2.1) : it should, in this case, put into action an obstacle avoidance module.

6. AREA CONCEPT LEARNING

Here we inderstand "learning" as the recognition of area concepts such as doors, rooms and corridors. This is done by the analysis of the decomposition tree of the graph. We first consider that a room is a biconnected or triconnected component in the de­ composition tree, and a door or a corridor is an edge linking two components. Yet, this approach is limited. In the analysed example, cell 25 cannot be viewed as a door as is the case of cell 24 ; both of them are separation nodes (edges in the decompo­ sition tree) ; metrical considerations must be in­ troduced to improve the Labelling. Examples of rules used are :

• Two adjacent biconnected components which are not edges, are Labelled as two different rooms if their common separation node is a cell with a small surface.

• -Two adjacent biconnected components, one being an edge, are labelled as one room, if their common separation node is a cell with a large surface.

Fig.4 presents two possible labellings corresponding to whether cell 3 is considered as small or large. In fact, we can improve the labelling by other criteria : for example the frequency of cell crossing. All considered, the decomposition tree is a "skeleton" which is used as a basis for area con­ cept learning. The tree is the model of the room connectivity graph.

7. AREA RECOGNITION

This paragraph presents more prospective ideas. The model of the robot increases as it explores the univers. In a rather complex case, the robot may reach a room already known through doors and corri­ dors unknown to it. It must recognize this area. Several means of recognition are possible :

1. The metrical i denti Hcation with absolute coordi­ nates. This may be inefficient due to uncertain­ ties in measurement and to robot positioning errors.
2. The identification of characteristic objects in the room if these exist.
3. A third possibility is topological recognition. The above structuring of space permits to solve this recognition as a subgraph isomorphism problem. The general problem is NP complete (even in the pla­ nar graph). We can nevertheless expect a solution through the labelling of the graph (approximate me­ tric, number of obstacles in the rooms, number of doors, ..· ) and through the reduction of the general problem to isomorphism of planar graph (for which efficient algorithms, based on the same graph decom­ position techniques, are known (/7- 9/).

8. CONCLUSION

The learning procedures presented in this paper lead to a significant improvement in the robot navi­ gation system. Furthermore, they enable a model­ ling of space at a high level of abstraction, and a labelling of subspaces close to human concepts of area. Orders such as : "Take corridor C and enter into room R through door D" will refer for the robot to data structures-wlth precise algorithmic meaning. While carrying out this research on learning by data structuring, we have developed original and efficient algorithms for planar-graph processing.