Qualitative theories on shape representation and movement. Application to industrial manufacturing and robotics

Abstract

From the end of 80's there has been a great interest in the study of qualitative models to represent and to reason with spatial aspects. The present work is centred in the development and application of a model to reason about the shape and about the movement in a qualitative way, which means in a way similar to the human reasoning. The interest of this study is originated in the necessity of solutions for the recognition of objects and the description and reasoning about the movement in situations with high uncertainty, as it is the case of robotic applications, where robots only have limited and vague sensorial information. In these situations the use of a qualitative reasoning, that allows us to handle ambiguities and errors, will be the most suitable.<br/>The movement of an object can be considered as a shape whose topologic relation with its environment (considered as another shape) changes in the time. On the other hand the shape of the objects is a spatial aspect in itself, and again for its study we have used topological concepts. The recognition of objects is important during the movement of a robot since for the accomplishment of certain tasks the robot must be able to recognize the objects with which it is finding during its trajectory, since these objects can be landmarks or reference points that provides to the robot spatial information of its environment.<br/>Therefore this work will be centred in the study of three space aspects: the shape of the objects, the topology and the movement. Several works exist about the shape of the objects [Jungert 94; Park and Gero 99, 00; Chase 96, 97; Shokoufandeh, Dickinson et al. 02], on topology [Cohn, Bennet ET al. 97; Renz & Nebel 98; Egenhofer & Franzosa 91; Clementini & Di Felice 95] and on movement [Zimmermann and Freksa 93; Musto, Stein et al. 00; Musto et al. 99; Rajagopalan and Kuipers 94; Forbus 83; Muller 98a, 98b]. However, most of these works are theoretical and they have not been applied to robotics.<br/>This PhD thesis presents a motion model as a qualitative representational model for integrating qualitatively time and topological information for reasoning about dynamic worlds in which spatial relations between regions and between regions and objects may change with time. This qualitative integration of time and topology has been accomplished thanks to the definition of an approach with the following three steps: (1) the definition of the algebra of the spatial aspect to be integrated, which will be time and topology. The representation of each aspect is seen as an instance of the Constraint Satisfaction Problem (CSP); (2) the definition of the Basic Step of the Inference Process (BSIP) for each spatial aspect to be integrated. In general, the BSIP consists on given two relationships which relate three objects A, B, and C (one object is shared among the two relationships, for instance A is related with B and B is related with C), we will find the third relationship between objects A and C; and (3) the definition of the Full Inference Process (FIP) for each spatial aspect to be integrated which consists on repeating the BSIP as many times as possible with the initial information and the information provided by some BSIP, until no more information can be inferred.<br/>On the other hand, the theory for the recognition of shapes developed is able to describe several types of shapes, as they are regular and non-regular polygons, with or without holes, with or without curved segments and even completely curvilinear forms. The theory describes shapes considering qualitatively the angles, relative side length, concavities and convexities, and types of curvatures of their boundaries using only their relevant points, which are defined as vertices, and the initial, final point and point of maximum curvature of the curves. To describe shapes with holes, topological and qualitative spatial orientation aspects have been considered in order to relate the hole with its container. Each object is described by a string which describes its qualitative distinguished features (symbolic representation), which is used to match an object against the others. This theory has been applied, in an industrial domain, for the automatic and intelligent assembly of ceramic mosaics. Mosaics are made of pieces of different shapes, colours and sizes, named tesseraes, that once they are assembled they create a unique composition with high added value, due its artist and decorative value. Mosaics are made usually following a design describing the position of each tesserae in the final composition. The application developed in this dissertation, recognise individual tesseraes from pictures, which represent the tesserae coming over a conveyor, against a vectorial mosaic design. Therefore, the application returns the position of the tesserae in the mosaic together with the angle that a robot arm has to do when picking the tesserae by its centroid in order to leave it in the correct orientation inside the mosaic. On the other hand the simplest version of this theory, in concrete the part that describes regular and non-regular polygonal objects, jointly with the developed theory of movement has been applied too for the simulated navigation of a real robot, in concrete of the Khepera2 robot. This application consists in a world formed by two rooms connected by a corridor. The robot first learns the topological map of the world. Then in each room there is an object and the robot has to decide if both objects represent the same object or not, for that purpose the robot uses the movement theory to plan the way to do and to detect possible deviations during its moving, and finally by using the qualitative theory for shape matching developed decides if the objects has the same shape or not.