A multi-hierarchical symbolic model of the environment for improving mobile robot operation

A Multi-Hierarchical Symbolic Model of the Environment for Improving Mobile Robot Operation Author: Cipriano Galindo Advisors: Dr. Javier Gonzalez Dr. Juan-Antonio Fernandez-Madrigal A MULTI-HIERARCHICAL SYMBOLIC MODEL OF THE ENVIRONMENT FOR IMPROVING MOBILE ROBOT OPERATION C. Galindo PhD Thesis in Computer Science Ingenier´ıa de Sistemas y Autom´atica Universidad de M´alaga M´alaga, SPAIN Marzo, 2006 AUTOR: Cipriano Galindo Andrades EDITA: Publicaciones y Divulgación Científica. Universidad de Málaga Esta obra está sujeta a una licencia Creative Commons: Reconocimiento - No comercial - SinObraDerivada (cc-by-nc-nd): Http://creativecommons.org/licences/by-nc-nd/3.0/es Cualquier parte de esta obra se puede reproducir sin autorización pero con el reconocimiento y atribución de los autores. No se puede hacer uso comercial de la obra y no se puede alterar, transformar o hacer obras derivadas. Esta Tesis Doctoral está depositada en el Repositorio Institucional de la Universidad de Málaga (RIUMA): riuma.uma.es UNIVERSIDAD DE M´ ALAGA DEPARTAMENTO DE INGENIER´ IA DE SISTEMAS Y AUTOM´ ATICA Dr. Javier Gonz´alez Jim´enez y Dr. Juan Antonio Fern´andez Madrigal, directores de la tesis titulada “A Multi-Hierarchical Symbolic Model of the Environment for Improving Mobile Robot Operation” realizada por C. Galindo certifican su idoneidad para la obtenci´on del t´ıtulo de Doctor en Inform´atica. M´alaga, Marzo, 2006 Dr. Javier Gonz´alez Jim´enez Dr. Juan Antonio Fern´andez Madrigal To Ana Bel´en Table of Contents Table of Contents vii 1 A Robotic Future 1 1.1 Whyisitnotreal? ............................. 2 1.2 Makingitpossible ............................. 8 1.3 Contributions of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Outline.................................... 11 2 A Multi-Hierarchical, Symbolic Model of the Environment 15 2.1 Introduction................................. 17 2.2 Informal Description of a Multi-Hierarchical ModelBasedonGraphs .......................... 21 2.2.1 What is an AH-graph? . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.2 What is a Multi-AH-graph? . . . . . . . . . . . . . . . . . . . . 23 2.3 Formalization of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 Formalization of Graph Abstraction . . . . . . . . . . . . . . . . . . . . 28 2.5 Category Theory for Abstraction and Refinement of Graphs . . . . . . 30 2.5.1 The Category of Graphs with Abstraction . . . . . . . . . . . . 31 2.5.2 The Category of Graphs with Refinements . . . . . . . . . . . . 37 2.6 Conclusions ................................. 41 3 Application of the Hierarchical Model to Mobile Robot Task Planning 43 3.1 Introduction................................. 45 3.2 Formalization of Classical Planning in Category Theory . . . . . . . . . 49 3.2.1 PlanningBasics........................... 50 3.2.2 The Category of Planning States with Abstraction . . . . . . . . 52 3.2.3 Functors between the AGraph and the AState Categories . . . . 55 3.2.4 Hierarchical Planning with CV AGraph∗and AState . . . . . . 62 vii 3.3 Hierarchical Planning through Plan Guidance . . . . . . . . . . . . . . 68 3.4 Hierarchical Planning through Action Guidance . . . . . . . . . . . . . 79 3.5 Anomalies in Hierarchical Planning . . . . . . . . . . . . . . . . . . . . 82 3.6 ExperimentalResults............................ 83 3.7 Conclusions ................................. 90 4 Multiple Hierarchies for Mobile Robot Operation 93 4.1 Introduction................................. 94 4.2 A Multi-Hierarchical World Model for a Mobile Robot . . . . . . . . . 97 4.2.1 Task-Planning Hierarchies . . . . . . . . . . . . . . . . . . . . . 98 4.2.2 Localization Hierarchy . . . . . . . . . . . . . . . . . . . . . . . 99 4.2.3 Cognitive Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.3 The Utility of the Multi-Hierarchical Model for Human-Robot Interaction . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.3.1 The Inter-Hierarchy Translation Process . . . . . . . . . . . . . 107 4.3.2 Interactive Task-Planning . . . . . . . . . . . . . . . . . . . . . 111 4.4 Conclusions ................................. 118 5 Automatic Learning of Hierarchies of Abstraction 119 5.1 Introduction................................. 121 5.2 The ELVIRA Framework . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.3 Model Creation/Maintenance . . . . . . . . . . . . . . . . . . . . . . . 126 5.3.1 Human-assisted Symbolic Modeling . . . . . . . . . . . . . . . . 127 5.3.2 Perceptual Anchoring . . . . . . . . . . . . . . . . . . . . . . . . 129 5.4 ModelOptimization ............................ 134 5.4.1 Evolutionary Hierarchy Optimizer . . . . . . . . . . . . . . . . . 136 5.4.2 Population.............................. 138 5.4.3 Individual Recombination . . . . . . . . . . . . . . . . . . . . . 140 5.4.4 Individual Mutation . . . . . . . . . . . . . . . . . . . . . . . . 144 5.4.5 Individual Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 147 5.5 ExperimentalResults............................ 149 5.5.1 RealEvaluation........................... 149 5.5.2 Simulated Experiments . . . . . . . . . . . . . . . . . . . . . . . 154 5.6 Conclusions ................................. 158 6 Implementation and Experiences on a Real Robot 161 6.1 Introduction................................. 163 6.2 Related Works on Human-Robot Interaction . . . . . . . . . . . . . . . 167 6.3 Overview of the ACRHIN Architecture . . . . . . . . . . . . . . . . . . 169 viii 6Why is it not real? SENSE PLAN ACT ENVIRONMENT Figure 1.3: Deliberative framework. •The environment can be accurately modelled. •Uncertainty is restricted. •The world remains unchanged during the planning and execution cycle. It is to be noted that these three assumptions can not be ensured in a real and uncontrolled environment, as the one described in the taxi example. A possible and well accepted solution within the robotic community is to follow a famous quote from Aristotle: In medio stat virtus1 That is, the best of each system can be adopted to solve our problem. The resultant framework, called the Hybrid paradigm (see figure 1.4) has now been widely accepted within the robotic community [6], [133]. Hybrid systems combine aspects from traditional AI, such as symbolic planning and abstract representations, with reactive capabilities to perform robustly under uncertainty. The use of a symbolic model of the robot environment enables it to consider global information to predict the best solution when performing tasks, as well as to adapt its overall behavior to perceived changes. 1All virtue is summed up in dealing justly. 1. A Robotic Future 7 SENSE ACT ENVIRONMENT PLAN Figure 1.4: Hybrid paradigm. The use of reactive techniques, for its part, provides robustness and quick operation to the robot, permitting it to react against abnormal and unforeseeable situations, i.e., a child crossing the street, running after her/his ball. We can conclude that hybrid frameworks provide a feasible solution to the problem of imitating human intelligence. But, in spite of such a conviction, our initial vignette is still fiction, why? The answer to this question involves a variety of scientific open issues, many of them out of the scope of this thesis. However, in our opinion, one of the main reasons for why the robotic future is not the present yet is that there is not enough knowledge about the way humans construct and use symbolic models, and thus, we can not reproduce this ability in machines. In general, it is clear that the modeling ability is learnt by our brain in the first years of our childhood, and that this ability is improved through our life [32], [33], but neither the internal biological mechanism to acquire new symbols, nor the way in which they are endowed with a particular meaning, are well understood yet. Then, will the robotic future be postponed up to the moment in which the scientific community figures out our most intimate mental processes? 8Making it possible 1.2 Making it possible The work presented in this thesis aims to contribute to the design of autonomous and intelligent robots able to work closely with humans. Probably, many years will pass (in the case that it happens someday) before researchers can discover the mental processes involved in our intelligent behavior. Moreover, if this spectacular discovery one day becomes true, it is not really clear the possibility of implementing such a mental process to construct intelligent machines [11, 19, 136]. In the meantime, we can approach the problem by taking short but steady steps. Obviously, the reader will not find, at the end of this manuscript, the design of RX342A, neither thousands of lines of code implementing its intelligent performance, but indeed, she/he could find new ideas, algorithms, mathematical formalizations and code implementation to enable mobile robots to face complex tasks within large environments. Considering this, we will outstandingly simplify the initial vignette turning it into a robotic application in which a mobile robot efficiently plans and carries out tasks, possibly managing volumes of information stemmed from a large indoor scenario, whereas it interacts intelligently with humans. The main elements involved in this approach are: •A Mobile robot. We focus on a mobile robot capable of performing with a certain degree of autonomy within human (and limited) environments, like office buildings, hospitals, etc. The robot has to account for a perceptual system that enables it to extract symbolic information from sensorial data, as well as to detect external stimuli, like obstacles. •Hybrid architecture. The hybrid paradigm is identified as the most convenient 1. A Robotic Future 9 framework to design mobile robots meant to perform autonomously and intelligently. •Large indoor environments. The robotic taxi driver (as well as any of us) has to deal with a vast amount of information. All this information comes from experience and should be stored and treated efficiently. In this work we consider large indoor environments, like office buildings or relatively small scenarios in which the robot manages large amounts of information. •Planning Efficiency. Efficiency in planning may turn into one of the bottleneck of hybrid architectures when the robot is supposed to perform in large-scale (or complex) environments. Thus, part of the effort of this work strives to reduce as much as possible the computational cost of the planning process. •Human Interaction. As in the taxi vignette, an intelligent robot needs to interact with humans. Such an interaction can be achieved by means of several mechanisms, for example via voice, through tactile or visual information, etc. In any case, the robot should be able to communicate to people using humans concepts, i.e. ”please take me to the High Tech Laboratory” The cornerstone of a deliberative agent, like the robotic taxi driver, is the way in which it models the environment. The performance of our robot, and therefore its level of autonomy and intelligence, will largely depend on how it learns, organizes, and uses the symbolic information stemmed from the environment. But, in spite of the marked benefits that the use of a symbolic representation may provide, it brings some problems among which the following stand out: (i) how the large amount of information arising from a real environment can be managed efficiently, and (ii) how the symbolic representation can be created and maintained along the robot’s 10 Contributions of this Thesis operational life. Problem (i) appears in complex scenarios, i.e. large environments like an office building, whose spatial model can contain thousands of concepts and relations between them. In this situation, the robot should account for appropriate mechanisms to efficiently cope with such amount of information. The solution adopted in this work is to endow the robot with the ability of hierarchically arranging the environmental information, classifying it at different levels of detail. Problem (ii), the creation and maintenance of the internal model, has not a complete solution yet, since the human mechanism for the creation of symbols that represent physical objects is unknown. This problem is derived from the widely known symbol grounding problem [66]. The main concern here is how to idealize a symbolic representation from a physical entity, and how to maintain such a model coherent with the world along the robot operation. This issue has been recently approached in the robotic field through anchoring [26], which is the solution adopted in this work. 1.3 Contributions of this Thesis The contributions of this thesis are the following: •The mathematical formulation of a multi-hierarchical symbolic model of the environment based on graphs. Such a model, formalized under Category Theory [123], copes well with the amount of information arisen from large scenarios. •The design and implementation of a computational framework that creates, maintains and reorganizes that symbolic world model over the operational life of the robot. This framework, called ELVIRA, implements an evolutionary algorithm to optimize over time the symbolic and hierarchical model of the robot world 1. A Robotic Future 11 with respect to its tasks and changes in the environment. •The implementation of a hierarchical planning approach, called HPWA, that boosts the robot task planning process by exploiting the hierarchical arrangement of its symbolic model. •A natural human-robot communication through the use of a particular hierarchy of the model, the so-called cognitive hierarchy. This hierarchy, typically constructed by a human, arranges space information in a way understandable by humans. Symbolic information from other hierarchies (devoted, for example, to task planning) can be translated to the cognitive one facilitating robot-human communication. •The design and implementation of a hybrid robotic architecture, called ACHRIN, that accounts for the previously mentioned features. ACHRIN has been tested on real mobile robots, like a robotic wheelchair for elderly people. 1.4 Outline The outline of this manuscript is as follows. Chapter 2 describes the mathematical model (based on hierarchies of abstractions) used in this work to symbolically represent the robot environment. This model, called Multi-AH-graph, has been previously presented in [45], and applied to the robotic field as partial results of this thesis in [43, 53, 54, 55]. In this chapter, a more elegant formulation of the Multi-AH-graph model based on Category Theory [123] is given. Chapter 3 details two general-purpose task planning approaches that improve outstandingly the robot task planning efficiency when using a hierarchical symbolic model. 12 Outline The proposed planning techniques are compared to other non-hierarchical planning approaches as well as to a well-known hierarchical planner in the robotic field (ABSTRIPS [124]). Chapter 4 studies the benefits of using multiple hierarchies to arrange symbolic information in different manners, each of them aimed to improve a particular robot operation, i.e. task-planning, self-localization, or human-robot communication [43]. That chapter also explains a symbol translation process, that is, a process that transforms symbols from a certain hierarchy into a symbol (or a set of them) of another hierarchy. This is especially significant when translating symbols from/to the hierarchy used for human-robot communication (the cognitive hierarchy). Chapter 5 describes a software framework, called ELVIRA, which provides a solution to the problem of creating and arranging symbolic information. We describe how a symbolic model can be created automatically or with human assistance, from spatial entities, like rooms, corridors, and simple objects. We also discuss how a possible large amount of symbols can be automatically arranged in order to enhance robot operations, i.e. robot task-planning. Finally, we also consider how the symbolic model can be adapted to reflect changes in the environmental information as well as changes in the robot operational needs, while preserving efficiency in the information processing. Chapter 6 deals with the design of a hybrid robotic architecture, called ACHRIN, that entails our hierarchical and symbolic world model (a Multi-AH-graph) as the principal part of its deliberative tier. ACHRIN, presented in [56], has been specifically designed for assistant robots in which there is a clear necessity for providing proper human-robot communication mechanisms. This is achieved by exploiting the high-level communication characteristic that the symbolic model offers. This chapter also shows some experiences carried out on a real mobile robot: a robotic wheelchair called SENA [62, 61]. 1. A Robotic Future 13 Chapter 7 summarizes the work presented in this thesis, pointing out our achievements as well as its main limitations. It also suggests some possible future lines of research based on this work. This document is completed by three appendices: Appendix A deals with mathematical demonstrations regarding the formalization of the categories presented in chapter 2. Appendix B presents mathematical demonstrations related to the formalization of our hierarchical task-planning under Category Theory. Finally, appendix C lists the planning domain considered in our experiences. Chapter 2 A Multi-Hierarchical, Symbolic Model of the Environment Do not worry about your problems with mathematics, I assure you mine are far greater. Albert Einstein How much information is stored in our brain? If we could measure it in a certain magnitude, let’s say megabytes, how many Mb should be necessary to represent all our knowledge? We do not only store a vast amount of data, but we also retrieve and use part of it, for instance, when thinking, remembering or solving problems. It is well stated in the psychologist literature that the key of such intellectual abilities relies on the way in which the human brain arranges the information [65], [68]. If our aim is to develop autonomous robots capable of managing the information arising from a human environment (like an office building), firstly, we have to devise an efficient arrangement of that information. In our work, we identify as ”efficient arrangement” a hierarchical organization of information based on abstraction. The term abstraction can be interpreted in different ways, but here, abstraction is understood as a process that reduces (abstracts) information in different levels of detail; for instance in a company, an employee can take 15 22 Informal Description of a Multi-Hierarchical Model Based on Graphs 2.2.1 What is an AH-graph? An AH-graph is a relational, graph representation of the environment which includes hierarchical information, that is, the possibility of abstracting groups of elements to super-elements. This kind of abstraction produces different layers isolated from one another, called hierarchical levels, that represent the same environment at different amounts of detail. Hierarchical levels in an AH-graph are multigraphs3. The lowest hierarchical level of the AH-graph is called the ground level, and represents the world with the maximum amount of detail available. The highest hierarchical level is called the universal level, and it typically represents the robot environment with a single vertex. Figure 2.2 shows an example of an AH-graph with a single type of relation representing ”rigidly joined”. Figure 2.2: An example of a single-hierarchical model (AH-graph) representing a possible abstraction of some spatial elements within a room. a) A 3D view of a room. b) Hierarchical levels that model the room (each of them is a flat graph), represented by different grey shades. c) Resulting hierarchy (each level contains a flat graph). Vertexes of each hierarchical level represent elements (or super-elements) of the 3In this document we also use the term ”graph” to refer to multigraphs [147]. 2. A Multi-Hierarchical, Symbolic Model of the Environment 23 world while edges represent relations between them with the possibility of holding weights representing the strength of those relations. For example, in mobile robotics, vertexes can represent distinctive places [88], while edges can indicate the navigability relation between them, with the geometric distance as the edge weight. A group of vertexes of a hierarchical level can be abstracted to a single vertex at the next higher hierarchical level, which becomes their supervertex (the original vertexes are called subvertexes of that supervertex). Analogously, a group of edges of a hierarchical level can be represented by a single edge (their superedge) at the next higher level (see figure 2.3). Besides the structural information captured by the AH-graph through vertexes, edges, and hierarchical levels, both vertexes and edges can also hold non-structural information in the form of annotations (see figure 2.4). This information may include, but is not limited to: geometrical data gathered from the environment (i.e.: maps of obstacles), costs incurred by the robot when executing an action (i.e.: an edge that represents ”navigability” from one location to another can store the expected cost energy of that navigation), etc. Non-structural information can be useful for planning and other algorithms. In particular, it is extensively used when the AH-graph model is employed for mobile robot navigation [43]. 2.2.2 What is a Multi-AH-graph? A single hierarchy (AH-graph) is the basis for constructing a multiple hierarchical model upon a common ground level. Broadly speaking, a Multi-AH-graph is a set of hierarchies interwoven in a directed acyclic graph structure, where each hierarchy is an AH-graph whose levels can be shared by other hierarchies (see figure 2.5). The number of shared hierarchical levels depends upon the power of detecting equivalence between 24 Informal Description of a Multi-Hierarchical Model Based on Graphs Figure 2.3: An AH-graph example. Vertex abstraction is shown with gray-shadow regions, i.e. vertexes {v1,v2,v3}are abstracted into the vertex v7. Notice how inner edges (inside each cluster) disappear in the abstraction process, while outer edges (thick lines) are abstracted to edges from the higher levels, i.e., edges {e2,e3}are abstracted to the superedge e6. hierarchical levels of the multi-hierarchy [45]. Using a symbolic, multi-hierarchical representation of the environment yields three important benefits: first, a multiple hierarchy permits us to choose the best hierarchy to solve each problem (i.e.: to adapt better to diverse problems, improving the overall efficiency, please refer to [46] for more detail); second, when several problems have to be solved, a multiple hierarchy provides the possibility of solving part of them simultaneously; and thirdly, solutions to the problems can be expressed in terms of the 2. A Multi-Hierarchical, Symbolic Model of the Environment 25 Figure 2.4: Example of an AH-graph holding annotations. This AH-graph models part of a typical office environment (a) through two hierarchical levels. Vertexes at ground level (b) hold point local maps while their supervertexes (c) hold the fusion of a number of them into a global map representing certain areas (rooms). 26 Formalization of Graphs Figure 2.5: An example of multi-hierarchy (with three hierarchies). In this directed acyclic graph, hierarchical levels are represented by dotted rectangular boxes, while arrows represent graph abstractions. Level A is the only ground hierarchical level of this multi-hierarchy, and level H the only universal level. concepts of any of the hierarchies, thus the information is given in the most suitable way for each specific purpose, as commented further on. In general, multiple hierarchies have proven to be a more adaptable model than single-hierarchy or non-hierarchical models [45]. This has been recently demonstrated in the particular case of graph search, which has a direct influence on mobile robot route planning [46]. 2.3 Formalization of Graphs This section gives a formalization of the classical flat multigraph model that will serve as the base of our multi-hierarchical model. A finite, directed, loopless multigraph Gis a tuple: G= (V, E, γ, ini, ter) 2. A Multi-Hierarchical, Symbolic Model of the Environment 27 where Vis the finite, non-empty set of vertexes,Ethe finite set of edges,γthe incidence function,ini the initial function, and ter the terminal function of the graph. The tuple satisfies the following requirements: V∩E=ϕ, V =ϕ(2.3.1) γ:E→(V×V− {(a, a) : a∈V}) (2.3.2) ini :E→V, ter :E→V, such that γ(z) = (ini(z), ter(z)) (2.3.3) If the incidence function is on-to4, the graph is called complete. If it is one-toone5, the graph is not a multigraph, but a conventional directed graph, or digraph (no parallel edges or loops exists). The incidence function γ(z) yields the vertexes connected by the edge z, for instance, γ(z)=(a, b). The initial vertex of zis the first element of the pair (a), also given by ini(z). The terminal vertex of zis the second element of the pair (b), also given by ter(z). Both aand bare said to be incident to z, and zis said to be directed from ato b, and to connect aand b(or indifferently, to connect band a). Any pair of edges that are directed from ato bare called parallel. By constraint 2.3.2, there may be more than one edge connecting the same pair of vertexes in any direction (parallel edges), but no edge can exist connecting a vertex with itself (loop6). By constraint 2.3.3, functions ini and ter are directly derived from the definition of the incidence function. Therefore, sometimes they may be omitted for the sake of simplicity. In this work, Vwill be referred to as V(G),Eas E(G), and γ,ini,ter, as 4A function is said to be on-to when every element of the range has a defined correspondence with an element in the domain. 5A function is said to be one-to-one when every element of the range that is an image of some element in the domain, is only image of one element. 6Those graphs that can contain both parallel edges and loops are called pseudographs. 28 Formalization of Graph Abstraction γ(G),ini(G), and ter(G)respectively, as long as the graph to which they belong must be specified explicitly. Vertexes are usually denoted by letters from the beginning of the alphabet: a, b, c, . . ., and edges by single letters from the end: z, y, z, . . . Two graphs Gand Hare called equal, written G=H, iff V(G)=V(H)∧E(G)= E(H)∧γ(G)=γ(H)(needless to say: ini(G)=ini(H)∧ter(G)=ter(H)). Otherwise, they are called unequal, written G=H. Obviously, G=H⇔H=G, G =H⇔H=G. The set of all the finite, directed multigraphs without loops will be denoted by Θ. Finite, directed, loopless multigraphs will be referred from now on symply as graphs. Usually, this type of graphs will be used for representing some portion of knowledge through concepts (vertexes) related by some relationships (edges), thus they are called by some authors conceptual graphs [27]. 2.4 Formalization of Graph Abstraction An abstraction from graph Gto graph His a partial7function between both graphs, defined as a tuple: A= (G, H, ν, ε) where Gis the graph that is abstracted, His the resulting graph, νis the abstraction function for vertexes, and εis the abstraction function for edges. The following restrictions must hold: ν:V(G)→V(H)is a partial function. (2.4.1) ε:E(G)→E(H)is a partial function. (2.4.2) 7A function is said to be partial when it is not defined for all elements of its domain. 2. A Multi-Hierarchical, Symbolic Model of the Environment 29 ∀z∈E(G), def8(ε(z)) ⇒[def(ν(ini(G)(z))) ∧def(ν(ter(G)(z)))] (2.4.3) ∀z∈E(G), def(ε(z)) ⇒[ν(ini(G)(z)) =ν(ter(G)(z))] (2.4.4) ∀z∈E(G), def(ε(z)) ⇒[ν(ini(G)(z)) = ini(H)(ε(z))∧ ν(ter(G)(z)) = ter(H)(ε(z)) ](2.4.5) Notice that this seems like a conventional graph homomorphism except for the partiality of εand ν, and for 2.4.4. The vertex ν(a) for a given vertex a∈V(G)is called the supervertex of a, or the abstraction of a. Analogously, the edge ε(z) for a given edge z∈E(G)is called the superedge of z, or the abstraction of z. In the case that νis total9, it will be also called complete. In the case that εis defined for every edge of Gexcept for those whose incident vertexes are abstracted to a same supervertex, it will be called complete. If both, νand εare complete, the whole abstraction is also said to be complete. In the case that both νand εare on-to, the whole abstraction is said to be covered. Functions νand εhave inverses defined as: ν−1:V(H)→power(V(G)) ∀b∈V(H), ν−1(b) = {a∈V(G):def(ν(a)) ∧ν(a) = b}(2.4.6) ε−1:E(H)→power(E(G)) ∀y∈E(H), ε−1(y) = {z∈E(G):def(ε(z)) ∧ε(z) = y}(2.4.7) where we write power(C) to denote the set of all the subsets of C. These functions are called refining functions for vertexes and edges, respectively. For any vertex a∈V(H), the vertexes belonging to v−1(a), if any, are called the subvertexes of ain G. Analogously, for any edge z∈E(H), the edges belonging to 8def(g(x)) indicates that g(x) is defined, i.e., that element xbelongs to the domain of function g 9A function is said to be total when every element of its domain has an image. 30 Category Theory for Abstraction and Refinement of Graphs ε−1(z), if any, are called the subedges of zin G. Constraints (2.4.1) and (2.4.2) define an abstraction as a special kind of morphism between graphs, composed of two partial functions. Notice that it is possible that an abstraction of a graph yields an isomorphic graph or the same graph (for that, both abstraction functions must be total). Also notice that, by constraints (2.4.3), an edge can not be abstracted if its incident vertexes are not, and by (2.4.4) an edge can not either if its vertexes have been abstracted to the same supervertex (in that case, the edge ”disappears” in H). Constraint (2.4.5) is the typical definition for graph homomorphism: when an edge is abstracted, the incident vertexes of its superedge are the supervertexes of the incident vertexes of the edge (that is, connectivity is preserved). The collection of all the possible abstractions between any pair of graphs is denoted by ▽. Sometimes we will need to refer to a component of an abstraction specifying explicitly the abstraction to which it belongs. For that purpose, a superindex will be used. For instance, G(A), H(A), ν(A), ε(A),[ν−1](A),[ε−1](A)refer to the components of a particular abstraction A. 2.5 Category Theory for Abstraction and Refinement of Graphs Category Theory has itself grown to a branch in mathematics, like algebra and analysis, to facilitate an elegant style of expression and mathematical proofs. A Category [35] consists of a collection of objects with a certain structure plus a collection of arrows (functions, also called morphisms) that preserve that structure): f:a→b 2. A Multi-Hierarchical, Symbolic Model of the Environment 31 Here aand bare objects and fis an arrow (a function) whose source is object a and target is object b. Such directional structures occur widely in set theory, algebra, topology, and logic. For example, aand bmay be sets and fa total function from ato bor, indeed, fmay be a partial function from set ato set b; or as we have formalized in this section, objects aand bcan be multigraphs, and fthe abstraction of graphs defined in section 2.4. Among the benefits provided by Category Theory we remark: •A single result proved in Category Theory generates many results in different areas of mathematics. •Duality: for every categorical construct, there is a dual, formed by reversing all the morphisms. •Difficult problems in some areas of mathematics can be translated into (easier) problems in other areas (e.g. by using functors, which map from one category to another) Next, the category of graphs with abstractions, AGraph, as well as its subcategories are formalized. For completeness, the dual of AGraph, the category of graphs with refinements (RGraph), is also stated. 2.5.1 The Category of Graphs with Abstraction The category of graphs with abstractions, that we will call AGraph, is similar to the well-known category Graph of digraphs with homomorphisms (very commonly used in graph rewriting and graph grammar literature [27]), except that it is defined under abstractions that are partial morphisms, and it does not allow empty graphs. Some other formulations of the category of graphs under partial morphism exists [76, 105], 38 Category Theory for Abstraction and Refinement of Graphs ∀z∈E(G),∀y∈α(z),[ini(H)(y)∈µ(ini(G)(z))∧ ter(H)(y)∈µ(ter(G)(z)) ](2.5.8) The collection of every possible refinement between graphs is denoted by ∆. For every abstraction A= (G, H, ν, ε) in AGraph between two objects Gand H, there exists one and only one refinement given by RA= (H, G, µ = [ν−1](A), α = [ε−1](A)). Since the definitions for ν−1and ε−1given in (2.4.6) and (2.4.7) satisfy (2.5.5-2.5.8), the category RGraph of graphs with refinements is the dual of AGraph. If the abstraction Ais covered, its refinement RAis called complete, and it satisfies: ∀a∈V(H(A)), µ(Ra)(a)=ϕ ∀z∈E(H(A)), α(Ra)(z)=ϕ(2.5.9) And if Ais complete, its refinement is called covered, and it satisfies: ∀a∈V(H(A)) ∪µ(Ra)(a) = V(G(A)) ∀z∈E(H(A)) ∪α(Ra)(z) = E(G(A)) (2.5.10) If Ais both covered and complete, then, considering (2.5.7), (2.5.9), and (2.5.10) together, a partition in graph G(A)is induced by µ(Ra)and α(Ra). The category RGraph can be now defined as a tuple: RGraph = (Θ,∆, ρ−, ρ+,I,•) where Θ is the collection of all possible non-empty, finite, directed multigraphs without loops, ∆ is the collection of all possible refinements on this kind of graphs, ρ−is the abstracted hierarchical level function, ρ+is the refined hierarchical level function, Iis the identity function, and •is the composition of refinements functions, such that: 2. A Multi-Hierarchical, Symbolic Model of the Environment 39 ρ−: ∆ →Θ (2.5.11) is a function that yields the graph that is being refined by a given refinement. That is, ρ−((G, H, µ, α)) = G. Also, ρ+: ∆ →Θ is a function that yields the graph resulting of a given refinement. That is, ρ+((G, H, µ, α)) = H. I: Θ →∆ (2.5.12) is a function that for any graph G yields a refinement that leaves it unalterated (or isomorphic): I(G) = (G, G, µG, αG), where11: µG:V(G)→power(V(G))αG:E(G)→power(E(G)) ∀a∈V(G), µG(a) = a∀z∈E(G), αG(z) = z And finally, •: ∆ ×∆→∆ (2.5.13) is a partial function that yields the composition of two given refinements R1,R2as long as H(R1)and G(R2)are equal (otherwise it is undefined). It is constructed as follows: R2•R1= (G(R1), H(R2), µ(R2)∗µ(R1), α(R2)∗α(R1)) where operations ∗(for edge and vertexes refinement functions) are defined as12: 11Notice that µGand αGare unique functions for graph G. 12Notice that this special composition of functions can be done only when H(R1)and G(R2)are equal. 40 Category Theory for Abstraction and Refinement of Graphs ∀a∈V(G(R1)), µ(R2)∗µ(R1)(a) = ∀b∈µ(R1)(a) ∪µ(R2)(b) ∀z∈E(G(R1)), α(R2)∗α(R1)(z) = ∀y∈α(R1)(z) ∪α(R2)(y) It can be demonstrated that R2•R1satisfies constraints for refinements of graphs (see appendix A.5). Composition of refinements is associative: ∀G, H, J, K ∈Θ,     ∀R1= (G, H, µ1, α1), R2= (H, J, µ2, α2), R3= (J, K, µ3, α3)∈∆, (R3•R2)•R1=R3•(R2•R1)     (2.5.14) This can be demonstrated based on the definition of •(see appendix A.6). And finally, ∀G, H ∈Θ,∀R= (G, H, µ, α), R•I(G) = R=I(G)•R(2.5.15) which can also be demonstrated based on the definitions of •and I(see appendix A.6.) Since constraints 2.5.13, 2.5.14, and 2.5.15 are satisfied under this definition of RGraph, then RGraph is a category. Notice that RGraph can also be decomposed in different subcategories (see figure 2.9). These subcategories are the dual of their AGraph counterparts: CVRGraph is the subcategory of graphs with complete, covered refinements, CRGraph is the subcategory of graphs with complete refinements (that is, covered abstractions), and VRGraph is the subcategory of graphs with covered refinements (that is, complete abstractions). 2. A Multi-Hierarchical, Symbolic Model of the Environment 41 Figure 2.9: Subcategories of the RGraph category. 2.6 Conclusions This chapter has noticed the relevance of using a certain arrangement of the symbolic information held by an agent for an efficient access and manipulation. This becomes clearly important when the amount of symbolic data is very high, which is the case when modeling complex and/or large-scale environments, like an office building. In our work we have relied on a multi-hierarchical and symbolic world model based on abstractions to arrange spatial information. Such a model, called Multi-AH-graph, will serve as the basis of the rest of this dissertation to improve the robot operation within large and human-populated environments. In this chapter, the Multi-AH-graph has been informally described as well as mathematically formalized under Category Theory. In the next chapter we use a single hierarchy from the multi-hierarchy to improve efficiency in robot task planning. Our hierarchical planning approach will be also formalized using Category Theory. Chapter 3 Application of the Hierarchical Model to Mobile Robot Task Planning Nothing is particularly hard if you divide it into small jobs. Henry Ford Planning tries to imitate the human decision-making process. In planning, a solution to a problem is given in the form of a sequence of basic actions that transforms a given initial situation of the environment into a desired or goal state. In scientific literature, special attention has been paid to issues such as robustness or soundness in planning, but efficiency has usually been pushed to the background (especially in robotics). However, apart from the correctness of solutions, efficiency should also be considered, especially in those applications in which the agent that plans is intended to work with large amounts of information. Let’s consider for a moment a variation of the taxi-driver vignette in which the driver must pick up a number of passengers at different places to head for a common destination1, i.e. an airport. The driver should decide the most convenient path with respect to time, gas consumption, 1Note that this is the salesman trip problem which is, like most of task-planning problems, NPcomplete. 43 44 and fares within the city. Under this non-trivial situation, would it be admissible if the driver takes a couple of minutes for deciding the path to the destination? However, although planning is quite simple for human beings, the computational process to plan a task is normally complex, taking large amounts of time and resources (memory). This issue becomes even worse when the planner operates with large environments, making the process very inefficient, even intractable. In this chapter, we focus on improving the efficiency of the robot task planning process by using our abstraction mechanisms. A general task planning approach which uses abstraction, called Hierarchical Task Planning through World Abstraction (HPWA for short) is described. HPWA boosts a general-purpose planner like Graphplan [15] or Metric-FF [73] by reducing information from the world model that is irrelevant for the tasks to be planned. 3. Application of the Hierarchical Model to Mobile Robot Task Planning 45 3.1 Introduction Robotic task planning has its origins in the more general problem of planning, which historically constitutes an important issue in Artificial Intelligence, being widely studied since the 1960’s. Besides robotics, AI planning has been particularized to a variety of problems such as path and motion planning [81, 89], assembly sequence planning [10, 31], scheduling [134], [158], production planning [138], etc. In general, the purpose of planning is to synthesize an abstract trajectory in some search space (also named state space, since it consists of possible states of the world), predicting outcomes, choosing and organizing actions of different types for reaching goals or for optimizing some utility functions. Maybe surprisingly, there are not many AI classical planners integrated into robotic architectures, mainly due to difficulties in connecting symbolic treatment of information (planning) to non-symbolic sources of data acquired from the real-world. In addition, the uncertainty and partial observability present in this type of applications make classical planning less promising than other approaches [74, 114]. Rather, most of planning in robotics uses specific algorithms intended to guide the execution of very particular robotic tasks (and not others) [3, 113, 137], as is the case of route planning for navigation. Among the few generic (in the AI sense) planners implemented for robotic architectures, some remarkable approaches are STRIPS [47], that was the first planner used for deliberation in a robot (the Shakey robot [20]), and PRODIGY [149], the planner of the Xavier mobile robot. Few of the works where classical task planners are employed for mobile robots have addressed the problem of computational efficiency, perhaps because they do not deal with a complex and large domains. However, this situation is easily encountered by a real mobile robot that moves within many different places, or when the robot may 46 Introduction interact with a lot of world objects, for example, when it is equipped with an on-board manipulator. Let’s think, for instance, of a mobile robot intended to deliver envelopes within an office building (which is the scenario used in our experimental results at the end of this chapter). In this scenario, employees can request the robot from their places to receive their daily post (see figure 3.1). Each time a request is commanded to the robot it has to plan a path to arrive to the mail room (maybe opening doors) under time and energy consumption restrictions, search a particular envelope (possibly removing others placed on top of the desired one) from a rack that may contain hundreds of them, and finally carry the post to a particular office. Moreover, in a real situation, the robot should also foresee moving to a energy recharger point with a certain frequency in order to keep itself operative. It seems a simple task that can be easily solved by humans, but it means a tricky goal to be achieved by the planning procedures of a mobile robot. The human advantage to face this type of tasks is our ability (i) to discard irrelevant information with respect to the task, i.e. rooms and envelopes not involved in the path between the office and the mail room, and (ii) to obtain high level plans which are successively refined, like ”go to the mail room”, ”take the post”, or ”go to the requested office”. A mobile robot lacking from these abilities should explore within a combinatorial space and consider all possible actions up to finding the optimal solution. In classical planning, the high computational cost of planning arising from this combinatorial search in state space2. This cost depends both on the complexity of the description of the states, and on the number of operators that can be applied to each state to obtain another. In the case of robotic task planning, the former corresponds 2Probability approaches to planning, which constitutes a more modern tendency to task planning under uncertainty, also suffer from efficiency issues, which can also be addressed through abstraction. 3. Application of the Hierarchical Model to Mobile Robot Task Planning 47 Figure 3.1: A typical scenario in which a mobile robot must face tasks that involve a large number of different possibilities within a large-scale environment. 54 Formalization of Classical Planning in Category Theory is a function that yields the planning state resulting of a given abstraction. That is, ϖ+((S, T, ξ, π)) = T. Besides, I:0→N(3.2.5) is a function that for any state Syields an abstraction that leaves it unalterated: I(S) = (S, S, ξS, πS), where: ξS:SN(S)→SN(S)πS:SP(S)→SP(S) ∀p∈SN(S), ξS(p) = p∀a∈SP(S), πS(a) = a And finally, 3:N×N→N(3.2.6) is a partial function that yields the composition of two given abstractions As1,As2as long as T(As1)=S(As2). It is constructed as follows: As23As1= (S(As1), T(As2), ξ◦, π◦) The two abstraction functions, ξ◦and π◦, are defined by mathematical composition, ξ◦=ξ(As2)◦ξ(As1)and π◦=π(As2)◦π(As1), such that: ξ◦:SN(S(As1))→SN(T(As2)) (partial) ∀p∈SN(S(As1)), def(ξ◦(p)) ⇔def(ξ(As1)(p)) ∧def(ξ(As2)(ξ(As1)(p))) ∀p∈SN(S(As1)), def(ξ◦(p)) ⇒ξ◦(p) = ξ(As2)(ξ(As1)(p)) (3.2.7) π◦:SP(S(As1))→SP(T(As2)) (partial) ∀m∈SP(S(As1)), def(π◦(m)) ⇒π◦(m)⇔def(π(As2)(π(As1)(m))) ∀m∈SP(S(As1)), def(π◦(m)) ⇒π◦(m) = π(As2)(π(As1)(m)) (3.2.8) The composition of abstractions is associative: ∀P, Q, R, S ∈0, ∀As1= (P, Q, ξ1, π1), As2= (Q, R, ξ2, π2), As3= (R, S, ξ3, π3)∈N, (As33As2)3As1=As33(As23As1) (3.2.9) 3. Application of the Hierarchical Model to Mobile Robot Task Planning 55 It also must be that: ∀S∈0,∀As= (S, T, ξ, π)∈N As3I(S) = As=I(S)3As (3.2.10) Since constraints (3.2.6), (3.2.9), and (3.2.10) are satisfied under this definition of AState, then AState is a category. Demonstrations of these constraints are similar to those given in appendix A.1 (please refer to it). A dual category, the Category of Planning States with Refinements (RState) can be also formulated by reversing every arrow of AState. Its formalization is analogous to the one presented here. 3.2.3 Functors between the AGraph and the AState Categories Informally, functors are functions that relate objects and arrows between two categories, preserving their structures. In this section we state a relation between objects and abstractions from AGraph (more precisely from CV AGraph∗) and AState in such a way that a graph will correspond to a state. This relation will serve to formalize our hierarchical planning approaches. But, previous to the formalization of the functor that relates CV AGraph∗to AState, we have to provide some auxiliary definitions. Definitions (3.2.7) and (3.2.8) provide the CV AGraph∗category with a system of types for both edges and vertexes. Definition (3.2.9) takes these types as a medium of linking graphs to states. Finally, definition (3.2.10) constructs the complete functor from CV AGraph∗to AState. Definition 3.2.7 (Edge-Predicate Translator).The Edge-Predicate Translator function, Γe, enriches the CV AGraph∗category, being the first step to transform graph 56 Formalization of Classical Planning in Category Theory edges into predicates. It is a partial function from the set of all possible set of edges of graphs8in CV Agraph∗,power(E(Θ∗)), to triples of all the possible predicate symbols Υ involved in AState. That is: Γe:power(E(Θ∗))→Υ×Υ×Υ ∀Z∈power(E(Θ∗)), def(Γe(Z)) ⇒Γe(Z) = (g, h, i) : g, h, i ∈Υ We impose that triples yielded by Γemust cover separatively the range of the function, that is:  ∪ {Zi∈power(E(Θ∗)):def(Γe(Zi)),Γe(Zi)=(g,h,i)} g = Υ  ∪ {Zi∈power(E(Θ∗)):def(Γe(Zi)),Γe(Zi)=(g,h,i)} h = Υ  ∪ {Zi∈power(E(Θ∗)):def(Γe(Zi)),Γe(Zi)=(g,h,i)} i = Υ (3.2.11) Notice that through Γewe can define a triple of predicate symbols for a set of edges taken from different graphs. A set of edges will correspond to three predicate symbols, the first and second one representing a type for their initial and terminal vertexes, respectively, while the third one represents a type for any edge of the set. In order to cover all the edges of E(Θ∗)with Γe, we impose it to define a partition over E(Θ∗), and thus, the following restrictions must hold:  ∪ {Zi∈power(E(Θ∗)):def(Γe(Zi))} Zi =E(Θ∗) 8For the sake of simplicity, we denote with E(Θ∗)the set of all those edges. More formally: E(Θ∗)=∪ G∈Θ∗ E(G). 3. Application of the Hierarchical Model to Mobile Robot Task Planning 57  ∩ {Zi∈power(E(Θ∗)):def(Γe(Zi))} Zi =∅ ∀Z∈power(E(Θ∗)), def(Γe(Z)) ⇒Z=∅ We also define the following three total functions for retrieving separately each of the three predicates yielded by Γe(they are total since Γeinduces a partition in E(Θ∗), and also onto by 3.2.11): Γe1:E(Θ∗)→Υ ∀z∈E(Θ∗),Γe1(z) = g:∃Z∈power(E(Θ∗))∧z∈Z∧ def(Γe(Z)) ∧Γe(Z) = (g, h, i) Γe2:E(Θ∗)→Υ ∀z∈E(Θ∗),Γe2(z) = h:∃Z∈power(E(Θ∗))∧z∈Z∧ def(Γe(Z)) ∧Γe(Z) = (g, h, i) Γe3:E(Θ∗)→Υ ∀z∈E(Θ∗),Γe3(z) = i:∃Z∈power(E(Θ∗))∧z∈Z∧ def(Γe(Z)) ∧Γe(Z) = (g, h, i) As commented before, Γeyields a type for edges and for their initial and terminal vertexes. However, sometimes it can be necessary to obtain a predicate from a set of connected edges of different types. For that, we will also need a partial function Γ∗ e that yields a language string given any set of edges: Γ∗ e:power(E(Θ∗))→Υ Remark 3.2.2.Functions Γeand Γ∗ eare functions that convert sets of edges of graphs into predicate symbols that represent the same graph-based relational information but in terms of a predicate-based language. 58 Formalization of Classical Planning in Category Theory Remark 3.2.3.Since Γe1, Γe2, Γe3, and Γ∗ eare onto, their inverses are always defined. Definition 3.2.8 (Vertex-Param Translator).The Vertex-Param Translator function Γvalso enriches the CV AGraph∗category, being a partial, one-to-one, and onto function from the set of vertexes of graphs9,V(Θ∗), to the set of all possible parameters Param of predicates of our first order language: Γv:V(Θ∗)→Param ∀a∈V(Θ∗),Γv(a) = r:r∈Param Remark 3.2.4.We will consider in the rest of this chapter that Γvis defined for all the vertexes of the graphs we will deal with. Remark 3.2.5.Since Γvis defined as a onto there trivially exists its inverse, denoted Γ−1 v, and since it is one-to-one, the inverse always yields one vertex. Definition 3.2.9 (Edge-State Translator).The Edge-State translator βGis a total function based on the definition of Γe, Γ∗ e, and Γv, that yields a set of logical predicates that represent the state of the world corresponding to the subgraphs of a given graph G. It is defined based on other four auxiliary total functions, β1 G,β2 G,β3 G, and β4 G: βG:power(E(G))→0 ∀Z∈power(E(G)), βG(Z) = [∪ z∈Z[β1 G(z)∪β2 G(z)∪β3 G(z)]]∪β4 G(Z), where β1 G:E(G)→0 ∀z∈E(G), β1 G(z) = {(Γe1(z) Γv(ini(z)))} β2 G:E(G)→0 ∀z∈E(G), β2 G(z) = {(Γe2(z) Γv(ter(z)))} 9As before, V(Θ∗)=∪ G∈Θ∗ V(G). 3. Application of the Hierarchical Model to Mobile Robot Task Planning 59 β3 G:E(G)→0 ∀z∈E(G), β3 G(z) = {(Γe3(z) Γv(ini(z)) Γv(ter(z)))} β4 G:power(E(G))→0 ∀Z∈power(E(G)), def(Γ∗ e(Z)) ⇒β4 G(Z) = {Γ∗ e(Z)a1, a2, . . . , an) : ai∈ {Γv(ini(z)) : z∈Z)} ∪ {Γv(ter(z)) : z∈Z)}∧∀i=j, ai=aj,} ∀Z∈power(E(G)),qdef(Γ∗ e(Z)) ⇒β4 G(Z) = ∅ Informally, βGrelates the types of edges and vertexes of the graph Gto predicates: β1 Gtransforms an edge into a predicate with one parameter (the initial vertex of the edge), β2 Gtransforms and edge into another unary predicate (the parameter is the terminal vertex), and β3 Gtransforms an edge into a predicate with two parameters (both vertexes). In its turn, β4 Gtransforms the subgraph induced by a set of edges into a single predicate with as many parameters as distinct vertexes are in that subgraph, if Γ∗ eis defined for that set of edges. This covers most of the possibilities of transforming a graph that represents a portion of the world into a state with equivalent information. Table 3.2 and equation 3.2.12 below show the application of the Edge-State translator to some subgraphs of three sample graphs. Graph GGraph HGraph I Figure 3.2: Examples for the application of the Edge-State translator for three graphs, that is, βG,βH, and βI. 60 Formalization of Classical Planning in Category Theory βG({z}) = {β1 G(z)∪β2 G(z)∪β3 G(z)∪β4 G({z})}= {(Γe1(z)a),(Γe2(z)b),(Γe3(z)a b),(Γ∗ e(z)a b)} βH({x, y}) = {β1 H(x)∪β2 H(x)∪β3 H(x)∪β1 H(y)∪β2 H(y)∪β3 H(y)∪β4 H({x, y})}= {(Γe1(x)c),(Γe2(x)e),(Γe3(x)c e),(Γ∗ e(x)c e), (Γe1(y)e),(Γe2(y)d),(Γe3(y)e d),(Γ∗ e({x, y})c d e)} βI({z}) = {β1 I(z)∪β2 I(z)∪β3 I(z)∪β4 I({z})}= {(Γe1(z)d),(Γe2(z)a),(Γe3(z)d a),(Γ∗ e(z)d a)} βI({v, w}) = {β1 I(v)∪β2 I(v)∪β3 I(v)∪β1 I(w)∪β2 I(w)∪β3 I(w)∪β4 I({v, w})}= {(Γe1(v)h),(Γe2(v)g),(Γe3(v)h g),(Γe1(w)h),(Γe2(w)i),(Γe3(w)h i), (Γ∗ e({v, w})g h i)} (3.2.12) In our planning domains (that is, under our definitions of Γe), the planning state yielded by βG(z) (the first case in figure 3.2) might be: {(is-an-object a), (is-a-place b), (at a b)}, where is-an-object, is-a-place, at ∈Υ : Γe1(z) =is-an-object, Γe2(z) =isa-place, Γe3(z) = at, and Γ∗ e({z}) = at. That is, in this example, edge zindicates the position of an object in the robot workspace. Now, with the previous defined functions we can formalize the Graph-State Functor for the categories CV AGraph∗and AState. Definition 3.2.10 (Graph-State Functor).Functors are maps between categories that preserve their structures. A functor Fbetween two categories, i.e. Aand B, consists of two functions, one from the objects of category Ato those of B, and one from the arrows of Ato those of B. It is usual to denote both of these functions by the functor name. A functor Ffrom category Ato Bmust satisfy the following restrictions: ∀x∈Obj(A), F(I(x)) = I(F(x)), and ∀g, f ∈Arrow(A), F(f◦g) = F(f)◦F(g) (3.2.13) 3. Application of the Hierarchical Model to Mobile Robot Task Planning 61 where Obj(A) and Arrow(A) denote the set of all objects and the set of all arrows respectively from category A. Therefore, we define the Graph-State Functor, Ψ = (Ψo,Ψa), between the categories CVAGraph∗and AState, as follows: Ψo: Θ∗→0 Ψa:▽→N being both of them total functions. Informally, Ψ permits us to transform a graph into a state (a set of logical predicates) and an abstraction of graphs into an abstraction of states that preserves the former transformation. Using the Edge-State translator βG, we can formalize the Graph-State Functor for objects from CV AGraph∗and AState (noted as Ψo) as follows: Ψo: Θ∗→0 ∀G∈Θ∗,Ψo(G) = βG(E(G)) The Graph-State Functor for arrows, Ψa, permit us to transform a covered and complete abstraction of graphs into an abstraction of states that preserves the previous definition for Ψo: Ψa:▽→N ∀A∈▽,Ψa(A) = (Ψo(G(A)),Ψo(H(A)), τ, κ)(3.2.14) where functions τand κare defined as10: 10Γvis considered to be defined for our purposes for all the vertexes of the graphs that are translated into states through Ψo. 62 Formalization of Classical Planning in Category Theory τ(Ψa(A)) : Υ →Υ ∀z∈E(G(A)),(def(τ(Ψa(A))(Γe1(z))) ∧def(τ(Ψa(A))(Γe2(z))) ∧def(τ(Ψa(A))(Γe3(z)))) ⇔ def(ε(A)(z))∧ ∀Z⊆E(G(A)),∀z∈Z, def(ε(A)(z)) ⇔def(τ(Ψa(A))(Γ∗ e(Z))) ∀z∈E(G(A)):def(ε(A)(z)),     τ(Ψa(A))(Γe1(z)) = Γe1(ε(z)) τ(Ψa(A))(Γe2(z)) = Γe2(ε(z)) τ(Ψa(A))(Γe3(z)) = Γe3(ε(z))     ∧ ∀Z⊆E(G(A)),∀z∈Z, def(ε(A)(z)) τ(Ψa(A))(Γ∗ e(Z)) = Γ∗ e(∪ zi∈Z ε(A)(zi)) κ(Ψa(A)) : Υ →Υ ∀a∈V(G(A)), def(κ(Ψa(A))(Γv(a))) ⇔def(ν(A)(a)) ∀a∈V(G(A)):def(ν(A)(a)), κ(Ψa(A))(Γv(a)) = Γv(ν(a)) Figure 3.3 sketches all the possible relations established between the CV AGraph∗ and AState categories through Ψ. Restrictions given by equation (3.2.13) are demonstrated for the Graph-State Functor Ψ in appendix B, therefore Ψ is a functor. 3.2.4 Hierarchical Planning with CV AGraph∗and AState We impose a particular restriction to the possible complete, covered H-graphs we deal with. For our purposes, any abstraction Ai= (G, H, ν, ε) of CV Agraph∗must satisfy: ∀z∈E(G), def(ε(z)) ⇒    Γe1(z) = Γe1(ε(z))∧ Γe2(z) = Γe2(ε(z))∧ Γe3(z) = Γe3(ε(z))     (3.2.15) ∀Z⊆E(G), def(Γ∗ e(Z)) ∧ ∀z∈Z, def(ε(z)) ⇒ def (Γ∗ e(∪ zi∈Z ε(zi)))∧Γ∗ e(∪ zi∈Z ε(zi))= Γ∗ e(Z) 3. Application of the Hierarchical Model to Mobile Robot Task Planning 63 That is, the predicate types associated to the edges of a graph remain unaltered when those edges are abstracted. In order to formalize our Hierarchical Planning approach HPWA on the categories previously defined, we need a few more auxiliary definitions. Figure 3.3: The Graph-State Functor. Functor Ψ maps objects and arrows between the CV AGraph∗and AState categories. Its inverse is not always defined. Definition 3.2.11 (Parameter-Vertexes Function).The Parameter-Vertexes Function ηis a total based on Γvthat transforms a set of parameters from Param into a set of vertexes from V(Θ∗)as follows: η:power(Param)→power(V(Θ∗)) ∀P∈power(Param), η(P) = ∪ pi∈P Γ−1 v(pi) That is, function ηproduces a set of vertexes from a certain graph that represent a set of given parameters. 70 Hierarchical Planning through Plan Guidance PROCEDURE HPWA-1 (State Goal, AHGraph G):Plan w=LongestCompositionChain(G) A=AbstractionCompositionChain(G,w) Initial= Ψo(Gw) FOR i = w DOWNTO 0 Goali= ExtendedStateAbstraction(Goal,A,i) problem-space={Initial,Goali,domain-operations} plan=EmbeddedPlanner(problem-space) RelevantGraph=Induced-Graph(η(SP(plan))) IF (i =GroundLevel(G)) ReducedGraph=ℓ−((H, RelevantGraph, ν, ε)) Initial=Ψo(H) END END RETURN (plan) END Figure 3.5: Pseudocode of the HPWA-1 implementation. A plan constructed from a certain level of an AH-graph serves to reduce the amount of information at lower levels. In the pseudocode, the ExtendedStateAbstraction procedure yields the goal state at the i-th level of the hierarchy, and η(SP(plan)) yields the set of vertexes that represent the parameters involved in a plan. chain of abstractions of CV Agraph∗: Ξg={A13A23. . . 3Aw} that represents the initial state of the world viewed at different levels of abstraction, and given a Goal state expressed with information taken11 from the ground level of that H-graph12, noted as G0, the first step of HPWA-1 (and also of HPWA-2) is to compute a composition chain of wAState abstractions, Ξs, through the functor Ψ, obtaining a sequence of planning states that represent the initial state at different levels of detail. Then, HPWA-1 constructs a sequence of goal states (Goal, Goal1, . . . , Goalw) representing each of them the goal to be achieved in terms of the information taken at the corresponding levels of the H-graph. For instance, if Gwrepresents the most abstracted 11That is, µ(SP (Goal)) ∈V(G(A1)). 12Without generality lose, we assume here that the goal state is given at the ground level of the H-graph (the first graph of the composition chain, that is, G(A1)). Otherwise, the formalization of HPWA is similar, but only considering composition chains of length w−k, being kthe position of the graph within the H-graph in which the goal is given. 3. Application of the Hierarchical Model to Mobile Robot Task Planning 71 hierarchical level of the H-graph and Swthe initial planning state obtained via Ψo(Gw), Goalwis the goal to be achieved by the embedded planner. The sequence of goal states is computed by applying the extended abstraction of planning states EAbs to every arrow of the composition chain Ξs. Thus, Goaliis obtained by definition 3.2.18: ∀Ai∈Ξs, i > 0, Goali=EAbsAi(Goali−1) Once the sequence of goal states is computed, HPWA-1 starts by running an embedded planner (Graphplan or Metric-FF in our case) with Initial = Ψo(Gw) as the initial state, and Goalwas the goal to be achieved. With this pair of abstract initial and goal states, and a set of operators O(see figure 3.7 for an example), the embedded planner produces an abstract plan at level w, that we denote planw. Such an abstract plan at level w, composed of a sequence of instantiated actions that transforms the initial state into the goal state, will be used to discard irrelevant information at the next lower hierarchical level (w-1). It is important to remark that for our HPWA approach, the graph Gwfrom which the initial abstract state is produced remains unalterable during the whole planning process (that is, neither edges nor vertexes are added/removed). Only a sequence of intermediate planning states are produced by the embedded planner to achieve the corresponding goal state13. Given planwthat solves the goal Goalwat level w, HPWA-1 discards irrelevant information with respect to the task at hand by obtaining the parameters of planw, that is14, the set of symbols (world elements) involved in all instantiated actions of planw, through the function η(SP(planw)) (see figure 3.5). Therefore, η(SP(planw)) yields all vertexes from the abstract level Gwneeded to solve Goalwthrough planw. 13Also notice that those intermediate states might not be directly transformable into graphs since Ψ is not a bijection. 14A plan, as a sequence of logical predicates, can be also considered as a planning state, and thus, its set of parameters can be computed. 72 Hierarchical Planning through Plan Guidance Through such a set of vertexes, we can induce a subgraph on Gw, the so-called RelevantGraphw, that only models the (abstract) information that have been used by the task planning process: that is, it does not consider information which is irrelevant for planning the abstract task. In figure 3.4 vertexes of the successive RelevantGraphs obtained in that way are marked, while irrelevant vertexes are unfilled. After obtaining each RelevantGraphi, the next step is to plan the task at the lower hierarchical level (i-1), but only using those symbols which are relevant for the task. That is, we only consider information stemmed from the refinement of RelevantGraphi onto Gi−1. For that, and knowing the abstraction Ai= (Gi−1, Gi, νi−1, εi−1)∈Ξg, an arrow Ain CV AGraph∗is constructed, satisfying that: A= (H, RelevantGraphi, ν′, ε′) : [H⊆Gi−1∧RelevantGraphi⊆Gi]15 ∧           ∀z∈E(H):def(ε′(z)) ⇔def(εi−1(z)) ∧def(ε′(z)) ⇒ [(ε′(z) = εi−1(z)) ∧εi−1(z)∈E(RelevantGraphi)] ∀a∈V(H):def(ν′(a)) ⇔def(νi−1(a)) ∧def(ν′(a)) ⇒ [(ν′(a) = νi−1(a)) ∧νi−1(a)∈V(RelevantGraphi)]           The dual of this abstraction A, that is, the refinement RA, is: RA= (RelevantGraphi, H, µ′ i, α′ i) RAis always defined, since we are considering complete and covered abstractions, and it yields a graph H, such that H⊆Gi−1. Informally, His the refinement of RelevantGraphiand only contains the minimal set of symbols required to obtain a 15We indicate with H⊆Gi−1that His a subgraph Gi−1. A subgraph of a graph Gis a graph whose vertex and edge sets are subsets of those of G. 3. Application of the Hierarchical Model to Mobile Robot Task Planning 73 plan at level i. Therefore, symbols not involved in the generation of a plan at a certain level are no longer considered in the planning process at lower levels. Once the RelevantGraphiis refined (into the graph H), the planning process continues (until the lowest level of the model is reached16), taking Goal(i−1) as the goal state to be achieved now and Ψo(H) as the initial state, which is a reduced portion of the original state IS(i−1) (refer to figure 3.4 again). If at some step of refinement, no plan can be obtained, backtracking occurs and a new abstract plan must be constructed. a) b) Figure 3.6: Example of two different hierarchical models of a robot environment. For clarity, from the hierarchical level G0upwards, each vertex label includes its subvertexes’ labels. For example, in a), the Laboratory node is the supervertex of L1, L2, and L3. Also in a), it is gray-shaded the subgraph of each level that represents the relevant information for the example explained in the text. In order to illustrate the described HPWA-1 method, let us consider a relatively simple environment where a mobile robot with a manipulator on board has to perform different tasks involving a given object of the world named ”Box”. Figure 3.6 shows 16In the case that the original goal state uses information from a certain level of the H-Graph, say Gk, different from the ground one, HPWA-1 will stop at that level. 74 Hierarchical Planning through Plan Guidance this hierarchical model of the environment with three zones (a laboratory, a room, and a corridor), the mobile robot itself, and the box to be handled. In this model, a complete, covered H-graph with three hierarchical levels has been considered, and thus a composition chain of two abstractions of graphs is defined: A1= (G0, G1, ν1, ε1) A2= (G1, G2, ν2, ε2) Ξg={A13A2} The ground level of the H-graph,G0, has the maximum amount of detail (vertexes represent distinctive locations for navigation and manipulation), the first level, G1, is used for grouping vertexes of G0into three different areas (which allows the robot to reset odometric error through some sensor matching method [94, 95]), and finally, level G2, represents the world with the minimum amount of detail. In this example, given a graph G∈ {G0, G1, G2}, we define the following three sets of edges: Z={e1, e2, e3, e5, e6, e7, e8, e9, e11, e13, e15}, X={e0, e10, e14, e16}, Y={e4, e12, e17} such that: •Γe(Z) = (location, location, nav) : location, nav ∈Υ •Γe(X) = (object, location, at) : object, location, at ∈Υ •Γe(Y) = (robot, location, at-robot) : robot, location, at-robot ∈Υ That is, Γedefines, in this example, three different types of arcs: (1) those arcs that indicate the robot possibility of navigating (nav), and thus, the type of their initial and terminal vertexes as locations; (2) arcs that represent the position of objects (at), being the object represented by the initial vertex, and the location where it is, by the 3. Application of the Hierarchical Model to Mobile Robot Task Planning 75 terminal vertex. And finally, (3) the arc (in our example there is only one since there is only one robot) that represents the position of the robot (at-robot) for which its initial vertex is typed as robot, while the terminal one is as location. Γv, which is the function that transforms vertexes into parameters, simply takes the vertex label (shown in figure 3.6 inside the vertexes) as a constant string. This is a simple translator function that imposes that vertex labels must be unique across all levels of the H-graph. In this scenario, planning a task like for example ”pickup Box” implies to search a plan to achieve a ground goal state {(held Box)}(as the postcondition of the ”pickup” operator defined in figure 3.7). According to HPWA-1, this task is planned as follows. First, the composition chain of AState as well as the sequence of initial states for planning are computed through the functor Ψ. Thus: IS0= Ψo(G0), IS1= Ψo(G1), IS2= Ψo(G2) As1= Ψa(A1), As2= Ψa(A2) Through the abstractions of the composition chain Ξs={As13As2}, the goal state, {(held Box)}, can be expressed at every level of the hierarchy by applying the EAbs function. For this example it is: Goal0={(held Box)}, Goal1={(held Box′)}, Goal2={(held Box′′) With these goals to be achieved at each level, HPWA-1 starts by planning at level G2the abstract goal Goal2={(held Box′′)}: •Planning at the universal level G2 The initial state IS2for level G2is Ψo(G2), which, in this example, according to the type of edges, contains the following predicates: 76 Hierarchical Planning through Plan Guidance Ψo(G2)={(at Box’’ Floor1), (at-robot Robot’’ Floor1), (object Box’’), (location Floor1), (robot Robot’’), (location Floor2), (nav Floor1 Floor2)} Since e15 ∈Z,e16 ∈X, and e17 ∈Y, that is, e15 is a navigational arc, e16 indicates the location of an object, and e17 indicates the location of the robot (see fig. 3.6). The embedded planner is run with this initial state to solve the abstract goal Goal2={(held Box′′)}, finding the following solution: Plan2=(PICKUP Box” Floor1 Robot”) Notice that in CV AGraph∗, due to the manner in which graphs are translated into states, some abstractions may lead to a losing of relevant information for the planning process. For instance, in this example note that if the vertex Robot from level G0would have been abstracted to the vertex Corridor (see figure 3.6), information about the location of the vehicle would be lost at upper levels, and thus, the planning process would have been impossible. In our work we assume that the world information (provided by edges) relevant for the goal to be solved is maintained along the abstractions. (operator GO (params (<x> LOCATION) (< y > LOCATION) < z > ROBOT) (preconds (at-robot < z > < x >) (nav < x > < y >) ) (effects (del at-robot < z > < x >) (at-robot < z > < y >))) (operator PICKUP (params (< x > OBJECT) < y > LOCATION < z > ROBOT)) (preconds (at-robot << z > < y >)(at-object < x > < y >)) (effects (held < x >)(del at-object < x > < y >))) Figure 3.7: Definition of the operators used in the example of HPWA-1. Operator effects can add or remove logical predicates from the planning state. 3. Application of the Hierarchical Model to Mobile Robot Task Planning 77 •Planning at level G1 Now, the symbolic information involved in Plan2is computed through function η. In this case, η(SP(Plan2)) ={Box’’, Floor1, Robot’’} Then, we compute the subgraph of G2induced by η(SP(Plan2)), resulting a graph called RelevantGraph2(shown as a gray-shaded area at level G2in figure 3.6a). For this example, RelevantGraph2does not include the symbol Floor2, since it is irrelevant to solve the task (it does not belong to η(SP(Plan2)). RelevantGraph2is then refined down to level G1, where only subvertexes of its vertexes are considered, and thus, only world elements which are relevant when solving the task are refined. In this particular case no information is ignored at level G1, since the unique discarded vertex Floor2 has no subvertexes. Thus, at level G1, the initial state is: Ψo(G1)={(object Box’), (robot Robot’), (location Laboratory) (location Corridor), (location Room), (at Box’ Laboratory), (at Robot’ Corridor), (nav Corridor Laboratory), (nav Corridor Room)} provided that {e11, e13} ∈ Z,e14 ∈X, and e12 ∈Y. The goal state at this level is Goal1={(held Box’)}. A solution for this goal provided by the embedded planner is: Plan1= (GO Corridor Laboratory), (PICKUP Box’ Laboratory) 78 Hierarchical Planning through Plan Guidance Observe that the world element ”Room” does not appear in the plan (it is irrelevant for the task ) and therefore, the RelevantGraph1(shown shaded at level G1 in figure 3.6a) becomes a subgraph of G1. At the next lower level (ground level), all its subvertexes will be discarded. •Planning at the ground level G0 Finally, at the ground level, the predicates that model the initial state come from the refinement of RelevantGraph1, that does not contain the Room vertex. Thus, the initial state is obtained through the refinement graph Hof RelevantGraph1: Ψo(H)={(object Box), (object Table), (robot Robot), (location L1), (location L2), (location L3), (location C1), (location C2), (location C3), (at Box L1), (at Robot C3), (nav C3 C2), (nav C2 C1), (nav C1 L3), (nav L3 L2), (nav L2 L1)} Given that {e5, e6, e7, e8, e9} ∈ Z,{e0, e10} ∈ X, and e4∈Y. Observe that no vertex within the Room is included in this state, hence reducing the computational cost of planning17. The goal state at the ground level is {(held Box)}, which is finally solved as: Plan0= (GO C3 C2),(GO C2 C1),(GO C1 L3),(GO L3 L2),(GO L2 L1), (PICKUP Box L1) These actions are primitive actions that the mobile robot can execute, so this is the final plan for the original task at hand. 17This is only an illustrative example: more extensive results on the reduction in computational cost are presented in section 3.6. 3. Application of the Hierarchical Model to Mobile Robot Task Planning 79 3.4 Hierarchical Planning through Action Guidance Planning through Action Guidance (HPWA-2 for short) differs from the previously commented HPWA-1 in that HPWA-2 uses the abstract plans not only to ignore irrelevant elements, but also to guide refinement into lower levels. This can lead, in normal situations, to a higher reduction in computational cost than HPWA-1; however, due to the poorer look-ahead capability of this refining process, HPWA-2 is more sensitive to backtracking than HPWA-1 . Broadly speaking, HPWA-2 tries to solve individually each action of an abstract plan (that is, an instantiated planning operator). To do that, postconditions of every action of a plan are considered as goal states to be sequentially planned at the lower level of the hierarchy. Thus, a particular refinement of the parameters involved in each action postcondition must be selected. That is, a subvertex of those vertexes from the H-graph that represent the parameters of a postcondition pi(given by η(SP(pi))) must be selected. Figure 3.8 sketches the HPWA-2 algorithm. HPWA-2 starts from an abstracted plan, taking each action individually in order to refine it (to obtain a subplan for every of them) at the next lower level. The refinement of an action ai, that is, the process of refining its parameters, is carried out randomly18 in our current HPWA-2 implementation, and thus, the postcondition of a refined action ai, is computed by choosing a random subvertex of each vertex in η(postconditions(SP(ai))). The advantage of refining the abstract plan in this way is that the amount of information necessary to plan a unique abstract action is generally much smaller than 18Heuristics could be used, like selecting a border subvertex, that is a vertex adirectly connected to a vertex bsuch that their supervertexes are different, or the subvertex with the highest order, that is, the one which is connected the most to other ones, etc. Other techniques based on constraint propagation are also applicable to guide the subvertex selection process [9]. 86 Experimental Results Figure 3.10: Robot world hierarchy. Vertexes into a given shaded region are abstracted to the same supervertex at the next higher level. At the ground level symbols (labelled with ”E” for envelopes and ”L” for destinations) are grouped into vertexes that represent rooms, these ones into areas and finally, a vertex represents the whole environment at the universal level. 3. Application of the Hierarchical Model to Mobile Robot Task Planning 87 involved in the tasks (Eand L) have been selected arbitrarily from the robot world. All tasks involve navigation and manipulation operations, and some of the goals are reached in more than 40 actions. The whole robot world is composed of more than 250 distinctive places, 30 different objects that the robot can manipulate, and all the navigation and manipulation relations existing between these elements. Planning Time 0,1 1 10 100 1000 10000 6 12 24 48 Environment complexity (Number of Rooms) Time (s) Metric-FF GraphPlan Abstrips HPWA1+ GraphPlan HPWA2 + GraphPlan Figure 3.11: Planning a single fixed task in an increasing complexity environment (ranging from 6 to 48 rooms). While the CPU planning time grows exponentially using the conventional planners considered here (hierarchical and non-hierarchical), both HPWA methods exhibit a constant CPU time, since irrelevant information for the task is discarded. This plot only shows the time spent by planners: neither preor post-processing, nor communication burdens have been added. No result is shown for Metric-FF for 48 rooms due to the large computational resources demanded. Figure 3.13 shows the results of this experiment using HPWA-1 and HPWA-2 with Graphplan as embedded planner, HPWA-1 with Metric-FF , a hierarchical version of Graphplan using the hierarchies produced by ABSTRIPS, and the conventional planners alone (Graphplan and Metric-FF). Each chart shows the results of planning one task out from the ones shown in figure 3.12. It is clear the computational benefit of 88 Experimental Results Tasks #1, #2, #3 Take Envelopes E1, E2, or E3 Tasks #4, #5, #6 Carry Envelopes E1, E2, or E3 to locations L1, L2, or L3 Figure 3.12: The six tasks planned for the second experiment. Three different objects (envelopes) and three locations of the environment have been chosen at random to test the hierarchical planning methods versus conventional planning. Please, see figure 3.10 to find these objects and locations in the ground level of the AH-graph. hierarchical planning through world abstraction against both non-hierarchical planning and ABSTRIPS. Also, notice that planning time is not shown for the last three tasks (Task 4, Task 5 and Task 6) for Graphplan planner and ABSTRIPS, because Graphplan was not able to find a plan due to the large computational resources demanded and ABSTRIPS fails in finding a correct plan that solves the tasks due to violation of previously achieved preconditions when refining a plan (the same problem is reported in [79]). In all these plots we only consider the time spent by the embedded planner, without taken into account the pre-processing time taken by the hierarchical manipulation. Notice how HPWA-2 performs better than HPWA-1 in all tasks, except for the first two, because of the backtracking burden. Figure 3.14 compares the total time (which accounts also for pre-processing and communications) of HPWA-1 versus HPWA-2 when using Graphplan as embedded planner. In this case, HPWA-2 performs more inefficiently since backtracking increases the number of plans to solve. Also, observe how the total time of HPWA-1 is quite similar to its planning time (figure 3.13), since the additional cost of this method is negligible. 3. Application of the Hierarchical Model to Mobile Robot Task Planning 89 Figure 3.13: Planning time for the proposed tasks (in seconds) on a Pentium IV at 1.7 MHz with 512 Mbytes of RAM. Both non-hierarchical and hierarchical planners exhibit worse CPU time than HPWA methods. Moreover, HPWA-2 exhibits the best planning time for all tasks except for the first two ones due to backtracking situations. Notice that the planning time is not shown for Graphplan and ABSTRIPS in the last three tasks, because they were not able to end up with a solution. In all these plots we consider only the time spent by the embedded planner, without taken into account other pre-processing times. 90 Conclusions Total Algorithm Time 0 5 10 15 20 25 30 T1 T2 T3 T4 T5 T6 Time (s) HPWA-1 + GraphPlan HPWA-2 + GraphPlan Figure 3.14: Total time spent by our HPWA-1 and HPWA-2 implementations with Graphplan as embedded planner. Time of HPWA-2 is higher than HPWA-1 due to the extra pre-processing involved in backtracking. In spite of this apparently bad result, HPWA-2 performs better than other approaches in figure 3.13, even when they do not include the pre-processing and communication burden considered in this plot. 3.7 Conclusions In AI literature, task planning has not dealt with large domains, which is a common situation in mobile robotics. In these cases, task planning, even with the most modern improvements, can exhibit a high computational cost, even can become intractable (as shown in figure 3.13). This chapter has introduced a new scheme for task planning that takes advantage of a hierarchical arrangement of the robot model of the environment. This approach performs planning at a high level of abstraction of the world and then, recursively, refines the resulting abstract plan at lower levels, ignoring irrelevant world elements that do not take part in the abstract plan. 3. Application of the Hierarchical Model to Mobile Robot Task Planning 91 HPWA has been stated and formalized through Category Theory upon the categories of abstractions of graphs described in chapter 2. In particular, we have described two implementations of HPWA that embed other existing planners (Graphplan and Metric-FF) to solve planning at each level of abstraction of the world. Thus, we can benefit from any other kind of improvements on the embedded task planner. We have shown how our two implementations of HPWA have performed better than the embedded planners alone and other hierarchical approaches such as ABSTRIPS. This good performance is tightly coupled with the use of adequate hierarchies of abstraction. Adequate hierarchies can be obtained by using algorithms for the automatic construction of abstractions based on the task-driven paradigm [45] or the one described in 5, which is based on evolutionary algorithms. Chapter 4 Multiple Hierarchies for Mobile Robot Operation Science is organized knowledge. Wisdom is organized life. Immanuel Kant (1724-1804) Minds are like parachutes. They only function when they are open. Sir James Dewar, scientist (1877-1925) In this chapter we study the benefits of using a multi-hierarchical symbolic model of the environment in robotic applications. As presented in chapter 3, a hierarchy, that is, a sequence of graphs and abstractions of graphs, can improve efficiency in certain robot operations like task planning. In a previous work [46] it has been stated how these benefits are also present in other tasks, like routing. Now we follow the same inspiration and endow a mobile robot with different hierarchies upon a common ground level (obtaining a multi-hierarchical model) in order to improve not only task-planning, but also other operations, such as localization and user communication, simultaneously. Such a model may imply the necessity of translating symbols from one hierarchy to another, especially to the one used for human communication. This chapter also proposes a mechanism that copes with that translation. 93 94 Introduction 4.1 Introduction The human use of hierarchical symbolic structures for dealing with our daily life is well accepted ([65, 68, 86, 87]). As commented in previous chapters, humans use abstraction to reduce the huge amount of information gathered by our senses, hence constructing a hierarchy of concepts. Psychological evidences of that can be found in [69, 102]. Also, we have empirically demonstrated in chapter 3 the benefits of using a hierarchical arrangement of spatial information to reduce the computational effort of task planning. Moreover, it seems that humans also use multiple abstraction [112] (multiple hierarchies of abstraction built upon the same ground information) for improving our adaptation to different environments and different tasks. That is, having multiple hierarchies allows us to select the most convenient one to perform each operation. Some interesting ideas arise when exploring this multi-hierarchical paradigm [45]: •Hierarchies of concepts allow humans to perform operations more efficiently than using non-hierarchical, flat data. •The hierarchy of concepts that is good for a given operation depends on the sensorimotor apparatus of the agent and on the particular environment where it operates. •The hierarchy of concepts that is good for executing efficiently a given operation may be not so good to execute a different one. •Thus, it is desirable to construct more than one hierarchy upon the same set of ground elements if, for example, more than one task is to be performed, or when the agent has to operate in very complex or different environments. 4. Multiple Hierarchies for Mobile Robot Operation 95 How do we use multiple abstraction in our lives? Let’s consider our different points of view when performing different tasks. For instance, when we drive our car we consider junctions and streets with their directions, traffic signals (like speed limits and wrong way signals), etc. For this car driving activity, we plan paths considering such information; we group streets following urban districts and we usually take into account our previous experience to avoid traffic jams. In contrast, when we are pedestrians, our hierarchical space model changes substantially. Although it contains the same ground space elements, we neither need to take care of traffic signals (only traffic lights for pedestrians), nor to worry about traffic jams. We, as pedestrian, may group (abstract) spatial concepts, like streets, with respect to different criteria, in order to plan routes, for example, by choosing pedestrian streets as often as possible. In general, the same physical objects can be classified under different categories when employed in different tasks. Let’s consider how a toddler groups ground elements when playing with a brick set. She/he arranges elemental objects (bricks) to construct for instance a house, and thus, some bricks become the walls, others the roof, while other bricks make up the door of the house. However, she/he can physically (and also mentally) group the same objects in a different way (assigning them other, different concepts) to devise, for example, a dinosaur, in which now, some of the bricks that constituted the house walls may turn into a threatening head. Based on these ideas, in this chapter we propose a particular multi-hierarchical symbolic model (Multi-AH-Graph), which corresponds to a subset of the AGraph category presented in chapter 3, devoted to cope with different robot operations. Notice that each robot operation may require different arrangements of the symbolic data. Thus, we utilize a different hierarchy of our multi-hierarchical model to solve each particular robot task. Here, we focus on three specific robot tasks: (1) task-planning, (2) self-localization, and (3) human-communication. Note that any robotic agent intended 102 A Multi-Hierarchical World Model for a Mobile Robot HALL WEST CORRIDOR ROOM 1 Western Rooms Middle Rooms R1-1 R1-2 R3-1 WC2 WC3 WC4 R2-1 R2-2 WC1 H2 EC4 EC1 EC3 L1 L3 Distinctive Place a) c) Employee WC5 EC5 R3-2 R4-1 L2 L4 Robot b) H1 H2 WC1WC2 EC1 EC2 WC4WC3 WC5 EC5 EC4 EC3 L1 L2L3 L4 R1-1R1-2 R2-1R2-2 R3-1 R3-2 R4-1 Robot at Nav Nav Nav Nav Nav Nav Nav Nav Nav Nav Nav Nav Nav Nav NavNav Nav Nav Nav Nav Nav Nav Nav Hall Room1 Room2 West Corridor East Corridor Laboratory Room3 Room4 ROOM 2 EAST CORRIDOR ROOM 1 ROOM 2 LABOR ATORY Hall Room3 Room1 West Corridor East Corridor Room4 Laboratory Room2 Eastern Rooms EC3 EASTERN ROOMS MIDDLE ROOMS WESTERN ROOMS Environment d) Figure 4.3: Representation of an environment with different levels of abstraction. (a) The environment where a mobile robot may perform different operations. (b) Ground level: topology of distinctive places identified by exploring the environment. This will be the lowest hierarchical level of the Multi-AH-Graph. (c) Descriptive hierarchy for communications from/to human. This hierarchy represents the cognitive interface with the human driver. 4. Multiple Hierarchies for Mobile Robot Operation 103 with the human aid, so its length and shape may vary largely (see figure 4.3)4. For the case of spatial regions, vertexes of the hierarchical levels of our cognitive hierarchy will represent different groupings of distinctive places, defined by the human to directly match her/his cognitive map. Typically, local groups of distinctive places within a room are grouped into a supervertex that represents the room, groups of rooms and corridors are grouped into floors, floors are grouped into buildings, and so on. The main goal is to reproduce in the multi-hierarchical model the cognitive arrangement of the space made by the human who is going to communicate with the robot. The purpose of such a cognitive hierarchy is the improvement of the communication and understandability between the human and the vehicle. In this way, the person can request robot tasks using her/his own concepts (i.e., go to the copier room), at the same time that she/he can obtain robot information, for example results of task planning, by means of understandable terms (see section 4.3). It is also possible to construct in this way more than one cognitive hierarchy, for communicating to more than one human. We have used a quite simple construction process for the cognitive hierarchy (similar to the one presented in [84]). The user must select a number of vertexes from the common ground level (that represent observations) or from a certain level of the cognitive hierarchy (areas, regions, etc.) which will be abstracted to a vertex at the next higher level. Here it gains relevance the way in which the ground symbols are acquired. As we will expose in detail in chapter 5, acquiring symbolic information from sensorial raw data is an arduous problem not completely solved yet. A way of addressing it is the 4This is because the cognitive hierarchy provides the particular viewpoint of each user, which may largely vary from others’. For example, an employee can group a set of distinctive places from the coffee room into a spatial concept labelled as ”my rest room”, while the person responsible for its cleanliness could group them, plus places from the near lavatories, under the label ”the nightmare area”. 104 A Multi-Hierarchical World Model for a Mobile Robot topology construction based on observations described before. Another approximation can be a process that automatically detect distinctive places, like entrances to rooms [22]. The result of such a process (vertexes representing those distinctive places) will be the starting point in the human-guided construction. The user could name ground symbols, for instance ”entrance door to my office”, and group a number of them to create a supervertex with a special meaning for her/him, i.e. all these doors connect to the ”main corridor”. But as the reader may realize, the mechanism to automatically acquire symbolic information is not available yet (sometimes this is called the anchoring [26] problem). Thus, apart from the existence of an anchoring process to automatically acquire symbolic information, the user should also be enabled to provide ground symbolic information manually. For example, the user can guide the robot to a distinctive place that is of interest to him/her, though it could not be considered by the anchoring process, i.e. ”in front of my desk”. In this way a person can create a number of ground spatial symbols to represent the location of, for example, a cabinet, a window, or a pile of books, which may be jointly grouped with automatically acquired symbols, i.e. an observation, to make a supervertex that represents an entire room which could be labelled by the user as ”my office”. In any case, when vertexes at the ground level are (manually or automatically) created, geometrical information required for posterior robot operation, like maps, images, etc, can be automatically annotated. Edges can also be added to the model to indicate navigability (from the previous robot location to the current one) or position relations (a book is on the desk) [43]. In our experiences detailed in chapter 6, the user of a robotic wheelchair can use voice commands to create a distinctive place for navigation (”I am interested in this place, its name is <place-name>) or an abstraction of them (”The visited places up 4. Multiple Hierarchies for Mobile Robot Operation 105 to now are grouped into a room called <room-name>”). A representative example of a human-guided constructed cognitive hierarchy is depicted in figure 4.3. 4.3 The Utility of the Multi-Hierarchical Model for Human-Robot Interaction As commented, a multi-hierarchical model like the one depicted in figure 4.4 can be used by an intelligent agent to efficiently perform different tasks in a hierarchical fashion. In that case, hierarchical approaches to solve certain operations, like task or route planning [57] [46], may provide abstract solutions before a concrete ground solution is achieved. This feature becomes very interesting when the robot is intended to operate with humans. Recall the taxi driver vignette: when the user asks the robotic driver to go to a particular place, it can start driving immediately (after it plans a route) or, on the other hand, it can report the user with relevant information about the planned route before it is executed. Although the first case is common when we catch a cab, the second option should also be desirable. Nevertheless, in this latter case, the user could be overwhelmed if the driver gives her/him highly specified information, enumerating streets and junctions, while it would be more useful to provide only abstract information at different levels of detail (about areas or districts to be traversed). When the user is informed about the driver intentions, she/he can agree with the selected route to arrive to the destination, or in contrast she/he can advise an alternative one. In any case, abstract results from the planning process carried out by the driver should be communicated to the user in a proper way. In this example, the taxi-driver planning process uses a particular hierarchy (possibly automatically constructed) which may largely differ from the cognitive one, and 106 The Utility of the Multi-Hierarchical Model for Human-Robot Interaction Figure 4.4: An example of multihierarchy in which the cognitive hierarchy is highlighted. In this example we consider three different hierarchies for task-planning. Notice how hierarchical levels can be shared between different hierarchies. 4. Multiple Hierarchies for Mobile Robot Operation 107 thus, abstract symbols from the former could not be understandable by a human. In order to report properly abstract information from one hierarchy, i.e. a task-planning hierarchy, to the user, a symbol translation to the cognitive hierarchy is required. Such a translation, that can be used to shift concepts between any pair of hierarchies, is used in our work to enable humans to interact with the robot task-planning process [54, 55]. The main advantages of interacting with a task planning process are: 1. A user can command the robot a task that involves abstract concepts from the cognitive hierarchy while the robot can carry out the task on a different, more efficient one. 2. The user can reject or accept the proposed abstract plan that solves a certain goal. Also, particular parts of the abstract plan can be accepted or rejected. 3. The user can ask the robot for more details about a given abstract solution. Next, a general inter-hierarchy translation process that shifts concepts between hierarchies is detailed. Then, we describe an example of interactive task planning which involves symbol translations between the task-planning and the cognitive hierarchy described in previous sections. 4.3.1 The Inter-Hierarchy Translation Process The Inter-Hierarchy translation process is aimed to translate symbols between any pair of hierarchies of the multi-hierarchical model. Broadly speaking, our translation mechanism consists of refining5a certain symbol from a hierarchy down to the common 5The proposed translation process can be successfully applied to Multi-AH-graphs that are subsets of the CVAGraph category, that is, those multi-hierarchies for which the refinement and abstraction functions are defined for any graph and are complete and covered. 108 The Utility of the Multi-Hierarchical Model for Human-Robot Interaction ground level of the model6and then, abstracting the resultant ground symbols along the destination hierarchy. However, while the abstraction of a given vertex (supervertex) of a graph in AGraph is unique, its refinement yields a set of subvertexes. Notice that the translation process may not produce an unique symbol at the target hierarchy, since when refining a vertex, a variety of subvertexes are obtained which are possibly abstracted to different concepts in the target hierarchy. Let’s consider an example in which two hierarchies represent different spatial arrangement of the streets of a city to illustrate the translation process. One hierarchy, the ”Zip Codes Hierarchy” (H1), groups streets following the administrative division for the post service, and the other one, the ”Police Station Hierarchy” (H2), groups streets covered by a given police station. The formalization of both hierarchies (see figure 4.5) is as follows (for simplicity we have not considered edges since they are not involved in this translation process). Let the graphs (hierarchical levels) G0, G1, G2, and G3be defined as: V(G0)={s1,s2,s3,s4,s5,s6} V(G1)={Z1,Z2} V(G2)={PS1,PS2,PS3,PS4} V(G3)={South-PS,North-PS} and let abstractions on these graphs defined as: A0=(G0,G1,ν0,∅) A1=(G0,G2,ν1,∅) A2=(G2,G3,ν2,∅) 6Although it is not a restriction of the CVAGraph category, we assume that all hierarchies of the Multi-AH-graph share a common ground level. 4. Multiple Hierarchies for Mobile Robot Operation 109 where ν0(s1) = Z1; ν0(s2) = Z1; ν0(s3) = Z1; ν0(s4) = Z1; ν0(s5) = Z2; ν0(s6) = Z2 ν1(s1) = PS1; ν1(s2) = PS1; ν1(s3) = PS2; ν1(s4) = PS3; ν1(s5) = PS4; ν1(s6) = PS4 ν2(PS1) = SouthPS;ν2(PS2) = SouthPS;ν2(PS3) = SouthPS; ν2(PS4) = North Hierarchy H1is a two-level hierarchy defined by abstraction A0, while hierarchy H2 is a three-level hierarchy defined by the composition chain A1⋄A2. Figure 4.5: Symbol translation between two hierarchies. A simple model with two hierarchies that groups symbols from the ground level (streets) with respect to its zip code (left) and the nearest police station (right). Dotted regions remark clusters of the zip code hierarchy while solid areas show clusters of the other hierarchy. For clarity sake, edges have been obviated in this example. 110 The Utility of the Multi-Hierarchical Model for Human-Robot Interaction In this example the translation of a certain concept, let say Z1, from the ”Zip Codes Hierarchy” into the other hierarchy will provide us information about the police station(s) that cover all streets grouped under the Z1 zip code. Such a translation starts with the refinement of Z1, yielding the set of ground symbols (streets and junctions) belonging to the same administrative area: ν−1 0(Z1) = {s1, s2, , s3, s4} Since the ground level is common to both hierarchies7, subvertexes of Z1 can be abstracted now through the target hierarchy, yielding the set of police stations that offer service to all streets with zip code Z1: ν1(s1) = PS1, ν1(s2) = PS1, ν1(s3) = PS2, and ν1(s4) = PS3 That is, the translation of the symbol Z1 from the ”Zip Codes Hierarchy” to the first level of the ”Police Station Hierarchy” is the set {PS1, PS2, PS3}, which in its turn can be abstracted again to the symbol SouthPS. Observe that in this example the translation of the symbol Z1 produces three different symbols at the first level of the target hierarchy, but a unique symbol at the second level. Thus, the ambiguity caused by the translation process can be solved by moving up at the target hierarchy, at the cost of loosing information. Next section details a human interactive task-planning approach that uses this inter-hierarchy translation process. 7In fact, it is not necessary to refine symbols down to the ground level, but only to the first level that is common to both hierarchies. 4. Multiple Hierarchies for Mobile Robot Operation 111 4.3.2 Interactive Task-Planning Apart from the benefits for user communication, the user participation into the planning process may also improve its efficiency. In the hierarchical planning scheme explained in chapter 3, task planning efficiency was achieved by detecting and removing unnecessary details of the robot environment. Now, an additional mechanism to discard useless information when planning can be provided by user interaction: when the user rejects or accepts an abstract plan (or part of it), she/he may discard world information, probably implying a further simplification in task planning. The benefits of this appear clearer if the robot deals with a very large environment like a real building composed of several floors, elevators, and hundred of rooms and corridors. In this case the reduction of the amount of data may become extremely important in order to plan efficiently robot’s tasks. We propose here an interactive, hierarchical task-planning approach based on the scheme described in the previous section, that can be split into two phases (see figure 4.6). 1. The first stage consists of translating the user task request, which can be specified at any level of the cognitive hierarchy, to the task-planning hierarchy. It is done by refining the human concepts involved in the task until the shared ground level (see figure 4.5). To do this, a particular refinement of the concepts involved in the task is chosen8. For example, if the user request is ”go to Laboratory”, the human symbol (Laboratory) involved in this task can be moved down to the ground level, choosing as refined symbol L1, that represents the Lab entrance. Thus, the user task turns into ”go to Laboratory entrance”. Once the user task is specified at the ground common level, it can be solved through the planning 8This is similar to the action refinement procedure carried out in HPWA-2, described in section 3.4. 118 Conclusions process, the user may be informed about a set of different possibilities to solve a plan. She/he can select one out of the offered solutions based on her/his knowledge of the environment. For instance, following the previous example, the user can suggest the abstract plan: {(GO Hall East-Corridor), (GO EastCorridor Laboratory)}since she/he knows that it is not necessary to consider Room3 to arrive to the Laboratory. Thus, through the solution pointed out by the human, the planner can solve the task at the ground level considering only those symbols embraced by the ones suggested by her/him. In this example, the final plan at the ground level is (see figure 4.7): {(GO H1 H2), (GO H2 EC1), (GO EC1 EC4), (GO EC4 EC5), (GO EC5 L1)} 4.4 Conclusions This chapter has studied the use of different hierarchies upon a common ground level, that is, a multi-hierarchical model, to improve several robot tasks at a time, including human-robot interaction. In particular, we have focussed here on a translation process that enables the robot to communicate its intentions (the result of its planning process) to the user under such a multi-hierarchical fashion. With this, we have assumed that the robot possesses a hierarchical arrangement of information to efficiently plan its tasks, whose results are communicated in a humanlike manner to the user. What remains to ”close the loop”, that is, to permit the robot to autonomously and efficiently perform within a large environment, is to devise a mechanism to create and tune over time its multi-hierarchical and symbolic model. This can be carried out by methods like the one presented in the next chapter. Chapter 5 Automatic Learning of Hierarchies of Abstraction Intelligence is the totality of mental processes involved in adapting to the environment. Alfred Binet, psychologist (1857-1911) One thousand days to learn; ten thousand days to refine. Japanese proverb An agent intended to operate intelligently within complex environments (as the robotic taxi-driver of the initial vignette) should adapt its internal world representation to face new problems and to react to new situations in an efficient manner. The above two quotes summarize the key ideas of this chapter. On the one hand, it is common to relate the intelligence of an agent to its ability for adaptation. Informally, we usually consider as intelligent beings those that can face new problems or situations, that is, those that can adapt themselves to changes. On the other hand, it is clear that efficiency is largely tighted to the usual meaning of intelligence: it is common to consider more intelligent those beings that are able to solve problems (tasks) with less consumption of resources (time, energy, etc.). In this sense, an agent adapting to its environment should not only learn new information, 119 120 but it should also arrange it (refine in the japanese proverb) properly for an efficient use in the future. In previous chapters, we have exposed mechanisms that permit agents to perform efficiently its tasks through a (hand-made) multi-hierarchical model. In this chapter we go into the automatic creation and optimization (adaptation) of planning hierarchies within that multi-hierarchical model of the environment1. A framework, called ELVIRA, has been developed to acquire and to arrange hierarchically symbols that represent physical entities like distinctive places or open spaces. Such an arragement is tuned over time with respect to both changes in the environment and changes in the operational needs of the robot (tasks to be performed). This way, the work carried out by ELVIRA is aimed not only to represent correctly symbolic information stemmed from the environment, but also to improve over time the robot efficiency in task-planning. 1We only focus on the adaptation of planning hierarchies since task-planning in large environments is highly affected by environmental changes, as well as it is one of the most complex tasks that a robot may carry out. However, our approach can be extended to create/optimize other hierarchies of the model. 5. Automatic Learning of Hierarchies of Abstraction 121 5.1 Introduction The use of a symbolic representation of the environment becomes crucial in robotic applications where a situated robot is intended to operate deliberatively. In the literature there have been many types of environmental representations for robot operation (geometric [7, 63], probabilistic [143, 145], topological [24, 88], hybrids [116, 144], etc.). As commented in previous chapters, we are concerned with symbolic ones, in the sense that for deliberation, the information stored by the robot must represent the world through qualitative symbols (concepts) rather than by quantitative data acquired by sensors. Such a symbolic representation permits the robot to intelligently deal with the environment, for example for planning tasks as explained in chapter 3. However, maintaining a symbolic representation of the environment involves several important problems, some of then not completely solved or well understood yet. In this work we deal with three of them: (i) maintaining the coherence between the real world and the internal symbols, (ii) processing efficiently large amounts of information, which is an important problem in robots that work in real environments, and (iii) optimizing the model, that is, selecting among all the possible coherent set of symbols that one could use for modeling a given environment, the most appropriate for operating as efficiently as possible. Problem (i) is tightly related to the psychological symbol grounding problem [66]. In the mobile robotic arena, this issue has been simplified recently through the so-called anchoring [16, 26], although in other communities it is seen from different perspectives and denominations such as SLAM [64, 143] or visual tracking [4, 72, 130]. Anchoring means to connect symbols of the internal world model of an agent to the sensory information acquired from physical objects. These connections can be reified in data 122 Introduction structures called anchors, which contain estimations of some attributes of the objects. In that sense, an anchor is in fact a model of the corresponding physical object, and thus it can be used by the agent as a substitute for it, for instance in planning or when the real object is not visible. Notice that anchoring is not a static process, but it must update continuously the symbolic information (deleting old symbols, changing current ones’ attributes, adding new symbols) by updating the anchors. The problem of processing efficiently large amounts of information (problem (ii)) arises when real environments with a potentially huge amount of perceptual, quantitative information, are considered. In that case, the symbolic representation may also be large, and therefore it must possess a suitable structuring mechanism for enabling future accesses in the most efficient way. A common approach to that problem is the use of abstraction, which establishes different, hierarchically-arranged views of the world as we have seen in this thesis. This mechanism, which is used by humans to arrange knowledge [69], can be exploited to improve efficiency in task planning, as explained in chapter 3. Some examples of efficient processing achieved through the use of abstraction can be found in [45, 46, 53]. It has been demonstrated that the use of abstraction can reduce the cost of processing information significantly, and even can make some exponential problems tractable. Finally, optimizing the model (problem (iii)) arises since the robot does not carry out the same tasks all the time nor in the same environment. It should adapt to different tasks over its working life. Also, changes in the environment may lead to reduce the suitability of the current internal representation for task planning and execution, and thus require a better structure of symbols. Hence, there is a need for some procedure that tunes the symbolic representation dynamically, optimizing it with respect to the current knowledge of the tasks the robot has to plan and execute. This optimization procedure can be appropriately addressed by heuristic optimization techniques, i.e. 5. Automatic Learning of Hierarchies of Abstraction 123 evolutionary algorithms [8], as we will show later. In this chapter we focus on problems (ii) and (iii). For that purpose, we have developed an evolutionary algorithm that has been adapted to be executed as an anytime algorithm (that is, the longer the algorithm is executed, the better the constructed symbolic representation, but there is always a correct structure available for the robot). For dealing with efficient structuring of the model, we use our AH-graph model which has demonstrated its suitability for improving robot operation within large environments in previous works [45, 53]. To prove the suitability of our approach within a real robotic application, our method has been integrated into a general framework in which the symbol grounding problem (i) also fits. For coping with automatic anchoring, we use techniques for extracting topological maps from grid maps [22, 40], and also image processing techniques for anchoring objects [57]. In the literature, works can be found that endow mobile robots with a symbolic representation of the environment, most of them using topological representations [17, 141, 148, 153], and often for path-planning. They cope with the automatic construction of a symbolic representation of the robot space (topology), and thus, they approach the first commented problem when anchoring distinctive places from the robot environment to symbols in the topology. Some of them also apply this topological (or in, general hybrid) techniques to large environments by hierarchically arranging symbolic (and also some geometric) information [87, 92, 148]. However, not much attention has been paid to the optimization of that internal symbolic structure during the robot operating life. As Wah stated in 1989: ”despite a great deal of effort devoted to research in knowledge representation, very little scientific theory is available to either guide the selection of an appropriate representation scheme for a given application or transform one representation into a more efficient one” [152]. Nowadays, such an affirmation is still applicable and only a few works aim to organize symbolic information [140, 142], 124 The ELVIRA Framework but without pursuing the optimality of robot operation within dynamic environments. Our work focuses on this less explored direction. The framework presented here, that we call ELVIRA, has been fully implemented and tested through real and simulated experiments, demonstrating its feasibility for the automatic creation and optimization of large symbolic representations of the robot environment that are used for efficient task planning and execution. Next section gives a general view of our framework. Following sections are devoted to go into the two main functions of ELVIRA: section 5.3 focuses on the creation of ground symbols that make up the model, and section 5.4 delves into the automatic arrangement of such symbols into an efficient structure (hierarchy) for task planning. In section 5.5 some discussion and experimental results are presented. Finally, conclusions and future work are outlined. 5.2 The ELVIRA Framework Our framework enables a mobile robot to solve correctly and efficiently its tasks within a dynamic and large environment by automatically creating an anchored symbolic representation, which is adapted over time with respect to changes in both environmental information and the set of tasks that the robot must perform. The proposed framework, called ELVIRA, has been fully implemented as a computational system (fig. 5.1 shows the general scheme). It has two inputs: the task to be performed by the robot at each time, and the environmental information gathered by its sensors, and two outputs: a plan that solves the requested task as best as possible given the knowledge acquired up to the moment, and a symbolic structure anchored to the environmental information and optimized for the set of tasks that the robot has dealt with. 5. Automatic Learning of Hierarchies of Abstraction 125 We use sensorial information to create and maintain anchored symbols (rooms, distinctive places for navigation, and objects for manipulation), arranged in a planning hierarchy of the multi-hierarchical model of the environment. At the lowest level of the multi-hierarchy, vertexes represent distinctive places or objects from the environment while edges represent relations between them, i.e. navigability between places or location of objects with respect to others. Upon this common ground level, which varies over time to capture the dynamics of the environment, a planning hierarchy is automatically constructed and maintained to improve the robot operations. Figure 5.1: A general view of our framework ELVIRA. It is fed with both the information gathered by the robot sensors and the requested task. It yields the best known planning hierarchy adapted to the agent tasks and environment, and a resulting plan for the currently requested task. ELVIRA includes three internal loops -anchoring, planning, and optimization- (marked in the figure by dark-gray shaded regions) that run concurrently. As shown in figure 5.1, our framework carries out the automatic creation and adaptation (optimization) of the planning hierarchy through three processes, implemented 126 Model Creation/Maintenance by the Grounding Agent, the Hierarchy Optimizer, and the Hierarchical Task Planner. The Grounding Agent is responsible for maintaining the symbols of the ground level of the model anchored to the real world. The resulting anchored information is then hierarchically arranged by the Hierarchy Optimizer. The Hierarchical Task Planner is in charge of planning general tasks (not only navigation) and calculating the goodness of the planning hierarchy for that process. In our particular implementation, these processes are executed with periods denoted in figure 5.1 as τgrounding,τoptimizer, and τtasks. That is, every τgrounding time-units the ground symbolic structure is updated with the information collected by the Grounding Agent; every τoptimizer the optimization process works to improve the planning hierarchy; and every τtasks a task is required to be planned and executed by the robot2. Notice that this period-based scheme, which is very useful for evaluation purposes, can be changed into an event-based one with little effort. In the following, the internal processes of ELVIRA regarding to the creation/maintenance of the symbolic model (section 5.3) and the planning hierarchy optimization (section 5.4) are described in detail. 5.3 Model Creation/Maintenance All deliberative systems that rely on a symbolic representation of the robot workspace must face the symbol grounding problem [66] which is not completely solve yet. This problem, largely treated in the scientific literature [26, 32, 132, 135], is related to the genesis of symbols (concepts) stemmed from reality. From an objectivist point of view, in the case of symbols that represent physical objects, they can only be the result of 2This periodic sampling scheme implies that the internal world representation may be temporarily inconsistent with the environment. This case is not considered yet in our work. 5. Automatic Learning of Hierarchies of Abstraction 127 many observations plus a mental process able to extract similarities from data. But how does such a mental process work? How could a robot imitate such a human ability? As the reader may realize, the symbol grounding problems becomes one of those wonderful mysteries of our brain: how does a young child make up a symbol for trees?, and how can she/he recognize the image, captured from her eyes, of a non previously seen tree? These are questions that are out of our understanding now, but we are aware of their relevance for any system that accounts for intelligence. To cope with this issue, in this work we have largely simplified the robot acquisition of ground symbols by considering only distinctive places, open spaces, and simple objects (like coloured boxes), and providing two acquisition mechanisms that implements the Grounding Agent: a humanassisted mechanism, and an automatic process called perceptual anchoring proposed in [26, 93]. 5.3.1 Human-assisted Symbolic Modeling A naive solution to the symbol grounding problem is to include a human into the system to inform the robot when a new symbol must be created (or modified). Thus, we permit a human to become the Grounding Agent of ELVIRA (though she/he will not be the only one). The robot, on its turns, links available sensory information, like odometry, maps, camera images, etc., to the symbols when they are created. That information can be used by the robot, for instance, for localization, navigation or for human-robot interaction as was explained in chapter 4. This solution exhibits great advantages in certain robotic applications. For instance, in assistant robotics, in which both human and robot work closely, it becomes useful that the symbolic world model of the robot mimics as much as possible the human 134 Model Optimization the framework is intended to cover more interesting cases. For instance, we could use higher-level reasoning to predict changes in the configuration of furniture depending on the time of day. Also, we could use semantic knowledge to make predictions about objects which should or should not be present, e.g., a kitchen should usually contain a stove but not a bed. Failure of these expectations, like observing a stove while we expect to be in the bedroom, can be used to engage in a recovery process. Some preliminary work in this direction was reported in [57]. 5.4 Model Optimization As commented at the beginning of this chapter, efficiency in task planning and execution is a relevant ingredient to define intelligence. Although the creation and maintenance of a coherent internal model with respect to the real world is an unavoidable issue for the correct planning/execution of tasks, the proper arrangement of such a model is also significant for the robot success. A vast collection of symbols arising from a real scenario arranged in an inappropriate manner may turn the execution of robot tasks into an impossible mission. What is the purpose of a highly coherent and updated model when it is not useful, for instance, for planning or reasoning? One can compare this situation to a library which entails a wide and valuable collection of books stored out of any order (see fig. 5.3). Is that amount of valuable information useful when you have to spend days, weeks or even years to find what you are looking for? As books in libraries are ordered following some criteria to facilitate the search, symbols managed by autonomous agents should also be arranged for the ease of their manipulation. The question is: what is the most convenient way to organize symbolic information? In the case of a library, books are indexed by genre, title, or author, 5. Automatic Learning of Hierarchies of Abstraction 135 Figure 5.3: ”Order is never observed; it is disorder that attracts attention because it is awkward and intrusive” (Eliphas Levi). since most of searches are based on these keys. Following this idea, symbols from the internal model of a mobile robot should be arranged in a certain way to improve over time the most frequent tasks performed by the robot. This is the key point of the model optimization part of the ELVIRA framework. As commented, ELVIRA considers symbols to represent distinctive places and simple objects, which must be arranged properly in order to improve the robot tasks. We focus on hierarchical structures since they are helpful in coping efficiently with the huge amount of information that a mobile robot may manage [53]. But the number of different hierarchies that can be constructed upon a set of symbols (as well as the different permutations of a set of books on a shelf) turns the model optimization problem into a hard problem for which no polynomial-time algorithm is known to exist. A feasible solution to hard problems is the use of evolutionary algorithms. In particular if they can be used as any-time processes, that is, the more they work, the better is the solution [58, 147], we find a good approach to our problem since in our case, finding the best hierarchy to solve the robot tasks (the most frequent ones) involves testing all possible candidates in the combinatorial space of hierarchies. The reader can find a vast literature about the use of evolutionary algorithms, also called genetic 136 Model Optimization algorithms. Some examples are [48, 99, 109, 117], that use evolutionary processes for adapting the behavior of mobile robots, pose estimation, etc. Evolutionary approaches for graph clustering, similar to the model optimization process described in this work, can be found in [98, 121]. An analysis and in-depth classification of evolutionary computation can be found in [8]. Next section gives a general description of evolutionary algorithms, detailing the particular implementation adopted in our work. 5.4.1 Evolutionary Hierarchy Optimizer Evolutionary computation is a biological inspired technique that simulates the natural evolution of species in which only those individuals best adapted to the environmental conditions survive. In nature, individuals of a population are affected not only by the environment conditions (climate, food abundance), but also by the rest of individuals. Individuals that perform better than others have a higher chance to survive, and thus, a larger opportunity to perpetuate their genetic material. This evolutive process ensures the improvement of individuals over generations. Evolutionary computation, mimicking the natural evolution process, considers a set of individuals (population) that represent particular solutions to a problem to be solved, while the environmental conditions correspond to the evaluation of each solution (individual) with respect to a certain objective function. Such an objective function measures the individual adaptation to the particular problem we want to solve. Broadly speaking, evolutionary algorithms are iterative processes aimed to find a good solution to a certain problem (see figure 5.4 for a general scheme). Typically, the process starts from an initial population generated at random, in which each individual provides a solution to the problem at hand. The evolution of individuals (solutions) is 5. Automatic Learning of Hierarchies of Abstraction 137 carried out through genetic-based operators: recombination, that simulates the cross between two individuals in which genetic information is interchanged, and mutation, that simulates a sporadic change in individuals’ genotype. At each iteration (also called generation), individuals are evaluated with respect to the objective function. The result yields the degree of adaptation of each individual to the environment, that is, to the problem. Those individuals with the best results pass to the next generation with a high probability of recombination and/or mutation, while individuals with the worst results will not participate in the next evolution stage (they are eliminated). When applying evolutionary techniques to solve a problem some considerations must be set. First of all, it must be defined the vector of parameters that encodes a solution to the problem at hand, that is, we have to define the genetic material of each individual, which is normally divided in parts called chromosomes. Next, depending on the particular encoding of the genetic material, recombination and mutation operators must be properly defined to permit the evolution over generations. And finally, the ”evolution rules” must be set, that is, the process to select individuals that will undergo mutation and/or recombination and the process to select individuals that will be eliminated/maintained after each generation. In our work we have chosen typical evolutionary techniques, such as the roulette wheel for selecting individuals and elitism for keeping the best individuals over generations. We recommend [8, 119] for a further description of these and other techniques used in the implementation of evolutionary algorithms. In the model optimization carried out by the Hierarchy Optimizer within the ELVIRA framework, the search space is the set of all possible hierarchies that can be constructed upon a set of grounded vertexes (symbols). Thus, each individual of the genetic population represents a hierarchy of symbols. Therefore, we have to firstly 138 Model Optimization generation=0; P=Initialize(); Evaluate(P) repeat P’=Variation (P) Evaluate(P’) P=Select(P’) generation=generation+1 until end condition Figure 5.4: Pseudocode of a general scheme for evolutionary algorithms. There are three relevant processes: (i) V ariation which produces changes in a given population based on recombination and mutation operators. (ii) Evaluate which yields the adaptation of each individual to the problem to solve, and finally (iii) Select that decides which individuals deserve to pass to the next generation. give the set of parameters that univocally defines a hierarchy (a solution), the recombination/mutation operators that make possible the evolution of individuals over generations, and the objective function that guides the evolution process. 5.4.2 Population In our implementation, the Hierarchy Optimizer starts from a random population made up of individuals that encode the minimum set of parameters, called strategy parameters, to generate potential hierarchies (i.e., AH-graphs) upon the ground level maintained by the Grounding Agent. A hierarchy (an AH-graph) can be constructed by a clustering algorithm that groups vertexes and edges of a certain hierarchical level to produce the next higher level [45]. In our work we have implemented an algorithm that generates clusters given a set of seed vertexes (see its pseudocode in fig. 5.5). Applying it to a flat graph (given a set of seed vertexes), we create a set of clusters, each of them initially containing only one 5. Automatic Learning of Hierarchies of Abstraction 139 of the input seed vertexes. The rest of non-seed vertexes are iteratively added to the clusters following a deterministic order and the connectivity in the graph. Since a hierarchy is a sequence of clusterizations from a ground graph, we have defined an individual for the evolutionary algorithm as a set of chromosomes, in which each chromosome encodes a set of seed vertexes. Thus, and individual iarepresents a hierarchy with klevels, and is encoded as a vector of k-1 chromosomes, that is, as a vector of k-1 sets of seed vertexes: ia={c1, c2, . . . , ck−1}={{n1 1, . . . , n1 p},{n2 1, . . . , n2 m}, . . . , {nk−1 1, . . . , nk−1 r}} (5.4.1) where nq idenotes the i−th seed vertex at level q. Seed vertexes of the first chromosome refer to vertexes of the ground level (that is, symbols acquired directly by the Grounding Agent) while seeds from the other chromosomes refer by their index position to a cluster previously generated at a lower level. For instance, n2 i=jindicates that the cluster generated by the seed n1 jis considered as a seed for clustering the next hierarchical level. Figure 5.6 shows an example of the resultant hierarchy encoded by the 3-chromosomic individual (i={(2,8,10), (1,3), (2)}), which produces a 4-level hierarchy (including the given ground level). Once we have defined the individual representation, the next step is the definition of the genetic operators to make possible the evolution of a initial population up to a set of individuals that provide a good solution to the problem of hierarchy optimization. 140 Model Optimization PROCEDURE Clustering (Graph g, Seeds s):Clusterization cl cl=0 FOR i = 1 to size(s) cluster = new cluster( s(i) ) cl=cl + cluster END WHILE (UnclusteredVertexes==TRUE) FOR j= 1 to size(cl) ConnectedVertex(cl(j),out) FOR k=1 to size(out) IF (Unclustered(out(k)) cl(j)=cl(j) + out(k) END END END END RETURN cl Figure 5.5: Pseudocode of the implemented clustering algorithm. Initially it creates a set of clusters containing an unique seed (a vertex from the given graph). Clusters grow up progressively including connected vertexes in a deterministic order that do not belong to other clusters. The process finishes when all vertexes are clusterized. Notice that when the graph is not totally connected the algorithm can consider isolated vertexes as unitary clusters, in order to always end. 5.4.3 Individual Recombination The recombination operation aims to imitate the natural process of genetic crossing. In general, given two parents, new offsprings are generated combining parts of their genetic material. As commented before, the definition of genetic operators, like recombination, largely depends on the individual encoding, but there are a wide rage of general recipes such as selecting a cross-point in both parents to determine the portion of parents’ genetic information to be donated to the offspring, selecting multiple cross-points, or allowing multiple parent recombination. The study of the different possibilities of recombination is out of the scope of our work. Please refer to [8] for an exhaustive study. In our particular hierarchical optimization approach, we recombine two individuals (hierarchies) by interchanging part of their genetic information (clustering information), that is, individuals involved in recombination interchange a set of seed vertexes. 5. Automatic Learning of Hierarchies of Abstraction 141 Figure 5.6: Example of graph clustering. This is the resultant hierarchy encoded by the individual i={(2,8,10), (1,3), (2)}upon a given ground level after executing successively the clustering algorithm of figure 5.5. Seed vertexes are indicated by double circles. The result is that the original individuals are turned into two new individuals containing a mix of the original genetic material. Formally, our process to recombine two individuals is as follows. Given two individuals ind1and ind2made up of kand lchromosomes respectively, an index chromosome iis selected at random, where i < k, i < l : ind1={c1 1, . . . , c1 k}={{n1 1, . . . , n1 a}, . . . , {ni 1, . . . , ni w}, . . . , {nk 1, . . . , nk c}} ind2={c2 1, . . . , c2 l}={{n1 1, . . . , n1 d}, . . . , {ni 1, . . . , ni q},...,{nl 1, . . . , nl f}} 142 Model Optimization Let c1 iand c2 ibe the i-th chromosomes of individuals ind1and ind2respectively: c1 i={ni 1, . . . , ni w} c2 i={ni 1, . . . , ni q} We select now a cross point s(s < w, s < q) that determines the portion of seed vertexes to be interchanged and mixed from both chromosomes, as follows: c1 i∗={n1 1, . . . , n1 s, n2 s+1, . . . , n2 q} c2 i∗={n2 1, . . . , n2 s, n1 s+1, . . . , n1 w} The resultant individuals entail a different version of their original i-th chromosomes: ind1={{n1 1, . . . , n1 a},{n(i∗) 1, . . . , n(i∗) q},...,{nk 1, . . . , nk c}} ind2={{n1 1, . . . , n1 d},{n(i∗) 1, . . . , n(i∗) w},...,{nl 1, . . . , nl f}}(5.4.2) It is important to remark that our recombination process should not end after simply interchanging seed vertexes among certain chromosomes, since seed vertexes of chromosomes that encode a hierarchical level higher than the ground level do not represent ground vertexes, but clusters previously created from the information of lower chromosomes. In the same manner, a seed vertex from a certain chromosome can participate in the clusterization of higher levels. That is, a seed vertex of a chromosome represents in fact a hierarchy (that is, it extends its influence to both lower and higher chromosomes), which should be considered when combining individuals. Let’s see an example. In the individual i={c1,c2,c3}={(2,8,10),(1,3),(2)}represented in figure 5.6, the seed vertex 3 of c2, both refers to the cluster generated by the seed 10 of c1, and is referred by the unique seed of chromosome c3(2). Thus, for instance, changing the 5. Automatic Learning of Hierarchies of Abstraction 143 seed vertex 10 of c1during recombination should require moving the whole structure generated by such a seed to the receptor individual. The result of recombining the individual iwith another one h, in which their first chromosomes are combined at cross point 1 (using the ground level depicted in fig. 5.6), is then performed as follows (this is also depicted in fig. 5.8): h={ch 1, ch 2}={(3|13)},(1)} i={ci 1, ci 2, ci 3}={(2|8,10),(1,3),(2)}(5.4.3) By equation (5.4.2), the recombination of the selected chromosomes is: c(h∗) 1={3,8,10} c(i∗) 2={2,13} and the resultant crossed individuals are: h∗={ch∗ 1, ch∗ 2, ch∗ 3}={(3,8,10),(1,3),(2)} i∗={ci∗ 1, ci∗ 2}={(2,13),(1)} Notice that after the recombination process, an extra chromosome has been added to the individual h, at the same time that the individual ihas lost one. This is because the interchanged seed generates a fourth level in the hierarchy represented by the individual i. Thus, in our recombination process not only particular seeds are interchanged, but also particular individual characteristics like the number of chromosomes. The pseudocode of the individual recombination we have implemented is shown in figure 5.7.