INTRODUCTION TO SPATIAL REASONING 

SPATIAL REASONING 

INTRODUCTION

RESEARCH CONTEX

In the province of Quebec as throughout the Western world, the population is considerably aging. For now, we can only try to predict the multiple impacts this will have on our societies, but it is now undeniable that we will have to deal with new challenges in the decades to come [1]. One of them is the increasing number of people suffering from a type of dementia such as Alzheimer’s disease [2]. These people suffer a gradual deterioration of their cognitive abilities over a period ranging from three to ten years, causing the loss of their autonomy and hence, their ability to take care for themselves. Therefore, at a certain stage in the evolution of the disease, these people must be assisted continuously for the rest of their lives [3]. The researches on Alzheimer are progressing, and several breakthroughs have been made in identifying the various possible causes of it. However, in the near future, the physicians have no options to cure or prevent Alzheimer’s. We can accurately estimate that the disease will continue to ravage families for quite a number of years. Finally, the increase in the number of people requiring ongoing assistance combined with an aging population may cause a shortage of trained health workers, which will have the effect of causing enormous stress on our already fragile health system. Hence, it appears necessary to find technological solutions to address this complex problem.
The evolution of information technology and electronics now makes it possible to envisage different approaches to address this societal transformation. Technological assistance inside a home qualified as smart has positioned itself as a significant trend [4] giving a new hope in the effort to postpone the institutionalization of the elderly. A smart home can be seen as a technologically enhanced environment using sensors (e.g. electromagnetic contacts, motion detectors, touch pad, radio-frequency identification tags, etc.), processors integrated into the miniature objects daily living (fridge, coffee maker, clothing, heating, dishes, etc.) and intelligent software agents communicating with each other in a goal of cooperation in the sense of multi-agent systems [5]. These environments must take decisions while taking care to limit their intrusion in order to help the resident to perform its tasks without invading their privacy. For example, if a stove burner is open, the device, or rather the artificial agent associated with it, must have a good idea of the behavior of the occupant as the context in which it takes place (preparation of a meal) by communicating with other agents. Also, suppose the agent observes that water boils for over an hour due to an oversight by the resident related to his cognitive impairment. Then, it could ask the main system to assist him by sending a vocal or video prompt, or using a more discrete media (light, emoticon, beep, etc.) [6]. The message type must be chosen carefully in order to stimulate the brain reactivity of the individual so that he corrects himself his mistake. When continuous support is provided to a patient with Alzheimer, cognitive degeneration of the disease is slowed and the patient can remain independent longer [7]. The significant advances of Artificial Intelligence (AI) are driving us toward the  application of techniques resulting from fifty years of research to this new stimulating problem that is the technological assistance of people with declining autonomy. The first fundamental step is to be able to understand the ongoing Activity of Daily Living (ADL) of the inhabitant in order to identify potential problems that may interfere with its accomplishment. This difficulty is, in fact, a special form of a well-known problem in artificial intelligence, which is called plan recognition [8]. A plan corresponds to a sequence of elementary step representing a certain ADL. In our application context, the recognition of plans intends to interpret the behavior of a person to provide, timely, appropriate services without being rejected by the individual. It is why a growing community of scientists [9-11] like the UQAC team at the Laboratoire d’Intelligence Ambiante pour la Reconnaissance d’Activités (LIARA) [12, 13] are currently working on this specific problem of recognizing ADLs inside a smart home.

SPATIAL REASONING AND ACTIVITY RECOGNITION

Activity recognition consists to circumscribe a library of plans to extract a minimal set of assumptions. As shown on Figure 1.1. it is based: (i) on the observation perceived through the sensors as a result of interactions (actions) of the person with the environment, (ii) on a principle of selection of hypotheses (possible activities), and (iii) on a matching method between the observations and the plans from the library describing the activities that are potentially observable [12]. This library is an ontology that describes in a logical formalism, the concepts of actions and activities. Then, the term activity recognition refers to the fact that we presuppose the existence of an activity structure planned at the beginning by the observed entity (the patient). The result is that the assistant agent seeks to recognize from its knowledge base (library of plans). The objective of this agent is, after the recognition process, to be able to predict as accurately as possible future actions of the patient by minimizing the number of possible hypotheses [14]. Figure 1.1: Simple schema illustrating the recognition process [15] To achieve the recognition we have described, several discriminatory constraints of different natures (logical, probabilistic, temporal, etc.) must be used from which a shortlist can be made. For example, the activity CookPasta could be composed of the steps BoilWater and PutPasta having a sequential constraint specifying to do BoilWater before PutPasta (temporal constraint) [16]. A spatial constraint can be defined as the spatial state of one or many objects in relation to their environment meeting certain conditions, hi other words, this corresponds to a condition of spatial nature on one or more objects to fulfill the conditions for carrying out an activity. Spatial reasoning is the natural way of thinking of human beings and should be considered in the analysis for the recognition of ADLs. It should also be understood that an activity can be performed in a valid sequence in time, but still be incorrect due to problems of spatial nature. For example, an activity may seem correct, but due to bad orientation of an object, execution is wrong. The same thing can happen if each step is correctly detected, but at some point, an object is moving away rather than closer to the activity’s zone (the problem of distance). Therefore, it is of crucial importance to consider spatial aspects. However, the approaches in the field of activity recognition generally ignore it, even if they recognize its important role [17]. Moreover, ost of the existing works are largely theoretical and not tested or only experimented in a non-realistic context that does not allow determining their actual effectiveness [18]

ILLUSTRATION OF THE IMPORTANCE OF THE SPATIAL ASPEC

To illustrate the importance of exploiting the spatial information embedded in the applicative context of activity recognition inside a smart home, we present in this section a small scenario highlighting the limits of a system ignoring this aspect for recognition and for assistance. Since a significant number of examples concern kitchen activities as washing hands [11], cooking meal [12] and preparing tea or coffee [19], it seems a good lead to choose a similar example. We also need our activity to be simple, but be composed of at least some steps. Finally, many authors like [20] have identified important criterions to describe spatial relations, and so we will use them for our example.
Let be Peter a fictive elder suffering from a mild to moderate degree (stage 3 or 4) of development of the Alzheimer disease. Our fictive subject lives in an intelligent house possessing cutting-edge technology and a multi-agents software. The agents analyze the actions of Peter in order to assist him in his tasks if needed. Peter takes out a kettle from a cabinet and fills it with water. The system receives a signal from Radio-Frequency IDentification (RFID) tags detecting the movement in a three dimensional coordinate in space. Then, it detects a change in the flow of tap water (increasing) using an ultrasonic flow meter. It associates this signals to a basic action BoilWater that is part of two different activities in the library: MakeCoffee and MakeTea. These activities are very similar, and both begin with the three same basic actions: BoilWater, GetCup and FillCupWithWater.
The fourth chapter examines the theoretical, practical and experimental contribution resulting from this research. The first section describes the formal elements to extend the model of Egenhofer & Franzosa in order to incorporate it to an algorithm for ADLs recognition. The second section shows the implementation of this new model of recognition within an intelligent home based on RFID technology. The final part of the chapter discusses the process employed to validate the proposed model and presents a comparative analysis of results obtained with the main approaches in the field. Finally, the fifth and final chapter concludes the thesis by presenting a detailed account of the research project highlighting the contribution of this work over previous works. This chapter will also address the limitations of the approach and future works arising from this research. The chapter concludes with a more personal assessment of this experience of initiation into the world of scientific research.

Table des matières

CHAPTER 1 -INTRODUCTION 
1.1 RESEARCH CONTEXT
1.2 SPATIAL REASONING AND ACTIVITY RECOGNITION
1.3 ILLUSTRATION OF THE IMPORTANCE OF THE SPATIAL ASPECT
1.4 RELATED WORKS ON SPATIAL REASONING AND RECOGNITION
1.5 CONTRIBUTIONS OF THIS THESIS
1.6 RESEARCH METHODOLOGY
1.7 THESIS ORGANIZATION
CHAPTER 2 – SPATIAL REASONING 
2.1 INTRODUCTION TO SPATIAL REASONING 
2.1.1 WHY SPATIAL REASONING MATTER IN ACTIVITY RECOGNITION?
2.2 EXAMPLE OF WORK IN SR FOR NATURAL LANGUAGE
2.3 ALLEN’S TEMPORAL RELATIONS FOR QSR …
2.3.1 INTERVAL BASED RELATIONS
2.3.2 ALLEN’S RELATIONS FOR ID SPATIAL REASONING
2.3.3 EXTENSION TO MULTI-DIMENSION REASONING
2.4 EGENHOFER & FRANZOSA TOPOLOGICAL MODEL
2.4.1 TOPOLOGY BASIS FOR THE MODEL
2.4.2 FRAMEWORK TO DESCRIBE RELATIONS
2.5 REGION CONNECTION CALCULUS (RCC)
2.5.1 INTRODUCTION TO THE CALCULUS
2.5.2 FUNCTIONS AND THEOREMS OF RCC
2.6 DISCUSSION ON SPATIAL REASONING
2.6.1 QUANTITATIVE OR QUALITATIVE SPATIAL REASONING?
2.6.2 WHICH PRIMITIVE SHOULD WE USE?
2.7 CHAPTER CONCLUSION 
CHAPTER 3 – RELATED WORKS ON ACTIVITY RECOGNITION 
3.1 INTRODUCTION 
3.1.1 ACTIVITY OF DAILY LIVING DEFINITION
3.1.2 DEFINING ACTIVITY RECOGNITION
3.1.3 ACTIVITY RECOGNITION INSIDE SMART ENVIRONMENT
3.2 ACTIVITY RECOGNITION: CONSTRAINTS BASED CLASSIFICATION
3.3 LOGICAL BASED APPROACHES
3.3.1 KAUTZ’S FORMAL THEORY FOR PLAN RECOGNITION
3.3.2 OTHERS LOGICAL CONSTRAINTS BASED APPROACHES
3.4 THE TEMPORAL APPROACHES
3.4.1 JAKKULA&COOK
3.4.2 ANOMALY DETECTION & PREDICTION ALGORITHM ENHANCEMENTS
3.4.3 REVIEW WITH OTHERS TEMPORAL APPROACHES
3.5 SPATIAL CONSTRAINTS BASED MODEL
3.5.1 RIMER SYSTEM
3.5.2 CHEMOTACTIC MODEL
3.5.3 APPROACHES COMPARISON
3.6 MACHINE LEARNING AND PROBABILISTIC METHODS
3.7 CONCLUSION ON EXISTING WORKS ..
CHAPTER 4 – QUALITATIVE SPATIAL REASONING RECOGNITION MODEL 
4.1 INTRODUCTION
4.2 FORMALIZATION OF THE NEW SPATIAL RECOGNITION MODEL 7
4.2.1 PRIMITIVES DEFINITION
4.2.2 OBSERVATION AGENT
4.2.3 EVALUATION OF ACTIVITIES’PLAUSIBILITY
4.2.4 LIBRARY CIRCUMSCRIPTION
4.2.5 EXECUTION EXAMPLE
4.2.6 REVIEW OF OUR NEW QSRR MODEL.
4.3 IMPLEMENTATION AT THE LIARA
4.3.1 THE LIARA INFRASTRUCTURE
4.3.2 ALGORITHM IMPLEMENTATION
4.3.3 LIBRARY IMPLEMENTATION
4.4 EXPERIMENTAL PROTOCOL
4.4.1 THE CLINICAL TRIALS
4.4.2 TESTS REALIZATION PROTOCOL Il
4.4.3 SPATIAL ISSUES Il
4.5 RESULTS PRESENTATION
4.5.1 METRICS DEFINITION
4.5.2 THE RECOGNITION RATE (RR)
4.5.3 ANALYSIS OF THE CDR RESULTS
4.5.4 DISCUSSION ON THE ACDR RESULTS
4.5.5 EARLY DETECTION RATE
4.5.6 ERRONEOUS SCENARIOS .
4.5.7 EXPERIMENTS DIFFICULTIES
4.6 SUMMARY AND DISCUSSION
4.7 CHAPTER CONCLUSION 
CHAPTER 5 – GENERAL CONCLUSION 
5.1 REALIZATION OF THE OBJECTIVES
5.2 REVIEW OF THE DEVELOPED MODEL
5.3 LIMITATIONS AND FUTURE WORKS
5.4 PERSONAL ASSESSMENT ON THIS RESEARCH
APPENDIX A – GENERATED REPORT EXAMPLE
APPENDIX B- TEST SCENARIOS FOR EXPERIMENTS
B.I MAKE COFFEE
B.2 MAKE TEA
B.3 READ A BOOK
B.4 MAKE HOT CHOCOLATE
B.5 PREPARING COLD CEREALS
BIBLIOGRAPHIE

Télécharger le rapport complet