Perceptual Anchoring of Symbols for Action

1 Introduction

The focus of this paper is the connection between abstractand physical-level representations of objects in artificial autonomous systems embedded in a physical environment. We call anchoring the process of creating, and maintaining over time, this connection.

Anchoring must necessarily occur in any physically embedded system that comprises a symbolic reasoning component. A typical example is the problem of connecting, inside an autonomous robot, a symbol used by a symbolic planner to refer to a physical object to the data in a perceptual system that pertains to the same object. This connection must be dynamic, since the same symbol must be connected to new percepts when the same object is re-acquired. For instance, a robot may be asked to identify and track a specific person in a crowd using visual data and given a linguistic description.

Anchoring is related to symbol grounding, defined as the problem of how to give an interpretation to a formal symbol system that is based on something that is not just another symbol system [Harnard, 1990]. Anchoring is an important special case of symbol grounding where the symbols denote individual physical objects.

The recognition of the anchoring problem as a problem per se is a recent phenomenon. Although all existing robotics systems that comprise a symbolic reasoning component implicitly incorporate a solution to the anchoring problem, this solution is typical hidden in the code, and it is developed on a system by system basis on a restricted domain. To the best of our knowledge, the first domain independent definition of the anchoring problem was given in [Saffiotti, 1994], while the first attempt at a computational theory of anchoring was reported in [Coradeschi and Saffiotti, 2000]. The goal of this theory was to specify the functionalities and the representations needed to perform anchoring in a general way that is applicable to a large number of systems.

In this paper, we focus on one specific aspect of anchoring: the use of symbols to denote objects in actions and plans, and the anchoring of these symbols to objects in the world. Consider the action 'PickUp(A).' We are interested in the problem of how to anchor the symbol 'A' to the relevant physical object through perception. To do this, we start from the above theory of anchoring, and extend it in three ways. First, we make a distinction between the properties of 'A' which are needed to identify the physical object to be used for the action, and those which are needed to perform the action. Second, we introduce the concept of partial matching, where 'A' can be (tentatively) anchored to an object whenever a required perceptual property cannot be extracted from the sensor data. Third, we consider the use of indefinite references in the context of action. Definite references, like "the black suitcase,"are meant to refer to one specific object with given properties, while indefinite ones, like "a black suitcase" are meant to refer to an arbitrary object in a given class [Russell, 1905].

In order to clarify the use of anchoring, we show two experiments performed on a real robot. They illustrate how anchoring can be integrated in a robot architecture, and how its functionalities can be used to connect the symbols used by a planner to the data acquired by a vision system. The examples also show the essential difference between two ways to treat actions that involve an indefinite reference. This reference can be resolved by the symbol system (planner), or by the anchoring process.

2 A Basic Model of Anchoring

We summarize here the basic elements of the computational theory of anchoring defined in [Coradeschi and Saffiotti, 2000]. The theory considers an agent that includes a symbol system and a perceptual system, and it focuses on the problem of creating and maintaining a correspondence between symbols and percepts that refer to the same physical object. It consists of a static part and a dynamic part. The static part includes the following.

•  A symbol system  including: a set X = fx 1 ;; x 2 ;; : : :g of individual symbols (variables and constants); a set P = fp 1 ;; p 2 ;; : : :g of predicate symbols; and an inference mechanism whose details are not relevant here.
•  A perceptual system  including: a set  = f 1 ;;  2 ;; : : :g of percepts; a set  = f 1 ;;  2 ;; : : :g of attributes; and perceptual routines whose details are not relevant here. A percept is a structured collection of measurements assumed to originate from the same physical object; an attribute  i is a measurable property of percepts, with values in the domain D i . We let D = S i D i .
•  A predicate grounding relation g  P -  - D, that embodies the correspondence between unary predicates and values of measurable attributes.

Example.  may be a planner that includes the individual symbol 'A' and the predicate symbols 'large' and 'small.'  may be a vision system able to recognize suitcases: from the image shown in Fig. 1,  may extract two percepts  1 and  2 . Attributes computed by  may include 'color' and 'width.' The predicate grounding relation g may include the triple hsmall;;width;; 10i: this says that the measure 10 for an object's observed width is consistent with the predication of its being small. 1

The g relation concerns properties, but anchoring concerns objects. The following definitions allow us to characterize objects in terms of their (symbolic and perceptual) properties.

Definition 1 A symbolic description  2 2 P is a set of unary predicates.

Definition 2 A perceptual signature :  ! D is a partial function from attributes to attribute values. The set of attributes on which is defined is denoted by feat( ). ; = (!D) is the set of all .

Intuitively, a symbolic description lists the predicates that are considered relevant to the perceptual recognition of an object; and a perceptual signature gives the values of the measured attributes of a percept (and it is undefined for the remaining ones). The g relation can then be used to define a function match(;; ) that says whether or not the values in the perceptual signature are consistent with a given symbolic description .

1 For the sake of simplicity we consider here a very simple g. The g relation can be quite complex in real domains.

The dynamic part of the model tells us, at any time t, what properties are associated to symbols in , and what attribute values are associated to percepts in .

•  A description state DS t : X ! 2 P that associates each individual x with its symbolic description at time t.
•  A perceptual state PS t :  ! ; that associates each percept  2  to its perceptual signature at time t. If  is not perceived at time t, then PS t () is everywhere undefined. The set of percepts which are perceived at t is denoted by V t .

Example. Consider our previous example. At time t, the symbol system may associate property 'small' to symbol 'A' by having small 2 DS t (A). The perceptual system may extract the width of the two percepts in the image, and associate them with the perceptual signatures PS t ( 1 ) = 1 and PS t ( 2 ) = 2 such that 1 (width) = 10 and 2 (width) = 20.

The role of anchoring is to establish a correspondence between a symbol x used in the symbol system to denote an object in the world, and a percept  generated in the perceptual system by the same object. This is done by comparing the symbolic description DS t (x) and the perceptual signature PS t () via the match function, hence via the g grounding relation. In the previous example, the g relation includes the triple hsmall;;width;; 10i, therefore the description of 'A' and the perceptual signature of  1 can be matched, thus suggesting that the symbol 'A' might be anchored to the percept  1 .

The above correspondence is reified in an internal data structure , called anchor. Since new percepts are generated continuously within the perceptual system, this correspondence is indexed by time.

Definition 3 An anchor is any partial function from time to triples in X --;.

At every moment t, (t) contains: a symbol, meant to denote an object inside ; a percept, generated inside  by observing that object; and a signature, meant to provide the (best) estimate of the values of the observable properties of the object. We denote these components by sym t ;; per t ;; and sig t , respectively. If the object is not observed at time t, then per t is the 'null' percept ?, and sig t still contains the best available estimate. Intuitively, an anchor can be seen as an internal, sensori-motor level representation of a physical object - see Fig. 2.

In order for an anchor to satisfy its intended meaning, the symbol and the percept in it should refer to the same physical object. This requirement cannot be formally stated inside the system. What can be stated is the following.

Definition 4 An anchor is grounded at time t iff per t 2 V t .

We informally say that an anchor is referentially correct if, whenever is grounded at t, then the physical object denoted by sym t is the same as the one that generates the perception per t . The anchoring problem, then, is the problem to find referentially correct anchors.

3 Extending the Model

The above model provides the basic ingredients of a general theory of anchoring, with no assumption as to the task for which anchoring is performed. In this paper, however, we focus on the use of anchoring to connect symbols for actions to physical objects through perception. From this perspective, the anchoring process should make sure that the anchor: (i) represents a physical object which has the intended properties for the intended action, and (ii) contains information about the perceptual properties which are needed in order to perform the action. For instance, if the action is meant to pick up a green suitcase, then the anchor should represent an object which is a green suitcase, and its signature should include an estimate of the position and orientation of this suitcase.

3.1 Action properties

The match function makes sure that the anchor is adequate with respect to the properties stored in the description state, i.e., DS t (A). In order to make sure that the anchor's signature also contains the properties that are relevant for action, we extend the dynamic part of our model by including the following.

•  An action parameter state A t : X ! 2 P that associates each individual x with the set of properties that need to be known in order to act on the object denoted by x.

In our example, A t (A) would specify the position and orientation of the suitcase. In the following we call matching properties the set of predicates in DS t (A) and action properties the set of predicates in A t (A)

Note that the predicates in A t are not used in the matching process: these predicates only indicate that the corresponding attributes must be included in the anchor's perceptual signature . However, these predicates can be used as default assumptions about the expected properties of the object in order to start action before the object is actually perceived. For instance, we may have an expectation about the position of a suitcase: this expectation can be included in the signature of the anchor in order to start approaching that position until the actual suitcase is perceived. These expectations can also be used to focus the perceptual system.

Having a property in the action state or in the description state may affect the meaning of an action. In our "PickUp(A)" example, if the position is not included in the description state, then 'A' will be anchored to any green suitcase, irrespective of its position. If the position of a given suitcase in included in the description state, then 'A' will only be anchored to the specific suitcase at that position. The first setup encodes the action "pick up a green suitcase," while the second one encodes the action "pick up the green suitcase at the given position" [Saffiotti, 1994]. Note that the object of the action is denoted by an indefinite reference in the first case, and by a definite one in the second case.

3.2 Partial Matching

Some actions may affect the perceptual information which is gathered by the agent: for instance, moving closer to an object may allow the perceptual system to observe more properties of the object. For example, suppose that we are interested in a suitcase with a white label on it: depending on the distance and angle of the suitcase, the label may not be visible.

Recognizing the fact that not all attributes of a percept may be extracted at all times brings about the need to redefine the meaning of the match function: match(;; ) should check that the signature is consistent with the descriptor  for those attributes which have actually been observed, but it should ignore the ones which have not been observed. The following is a possible way to define the match function.

Intuitively, obs(p;; ) says that an attribute related to p (via the g relation) has been observed in , and cons(p;; ) says that the observations in are consistent with the p predicate according to g. match(;; ) returns ;; if there was a mismatch between some predicate in  and the observed values; otherwise it returns the subset of the predicates in  for which a (consistent) value has actually been observed.

It is useful to keep track of which of the predicates in the symbolic description for a symbol have actually been observed, and which ones have not. To do this, we extend the definition of an anchor to include a list of the observed predicates as follows.

Definition 3 (bis) An anchor is any partial function from time to tuples in X --;-2 P .

We write obs to denote the fourth element of an anchor (t).

4 The Functionalities of Anchoring

In order to turn the above model into a useful computational framework, we need to define which functionalities are needed in order to solve the anchoring problem for a given symbol x. In [Coradeschi and Saffiotti, 2000] three main functionalities have been identified: (i) to create a grounded anchor the first time that the object denoted by x is perceived; (ii) to update the anchor when we need to reacquire the object after some time that it has not been observed; and (iii) to continuously update the anchor while observing the object. Given the above extensions to the model, these functionalities can be defined as follows. (t denotes the time at which the functionality is called.)

Find Take a symbol x and return a grounded anchor defined at t, and undefined elsewhere. In case of multiple matching percepts, return one anchor for each of them. This is summarized by the following pseudo-code.

procedure Find (x;; t)  f 2 V t j match(DS t (x);; PS t ()) 6= ;;g if  = ;; then fail else for  i 2 f 1 ;; : : : ;;  n g =   i match(DS t (x);; PS t ( i )) i Attributes(A t (x);; PS t ( i );;  i ) i (t) hx;;  i ;; i ;;  i i return f 1 ;; : : : ;; n g

The Attributes function returns the part of the perceptual signature PS t ( i ) that only includes the "interesting" attributes, that is, those that correspond to either description properties or to action properties. (A specific implementation may also include attributes which are needed by the perceptual system to track the object, e.g., its position and velocity.)

Reacquire This function is used to find an object when there is a previous perceptual experience of it. Take an anchor defined at time t ; k and extend 's definition to t. First, predict a new signature ; then see if there is some new percept that is compatible with the prediction and the symbolic description; in case of multiple matching percepts, use a domain dependent selection function. If one percept is found, update . Prediction, verification of compatibility, and updating are domain dependent; verification should typically use match.

procedure Reacquire ( ;; t) x sym t;k  ;; Predict( sig t;k ;; x;; t)  Selectf 0 2 V t j Verify(DS t (x);; PS t ( 0 );; ) 6= ;;g if  6=? then  Verify(DS t (x);; PS t ( i );; ) Update( ;; PS t ();;DS t (x)) (t) hx;; ;; ;; i return

If Reacquire fails to find a matching percept, then (t)

contains the predicted signature and the 'null' percept ?. Note that in this case (t) is not grounded.

Track Take an anchor defined for t;1 and extend its definition to t. It is used in the special case of reacquisition whenever the object is kept under constant observation. Prediction is in general much simpler than in the Reacquire case, and verification is only made with respect to the previously perceived attributes via a domain dependent function MatchSignature. This functionality could for instance be implemented with a Kalman filter.

procedure Track ( ) x sym t;1 OneStepPredict( sig t;1 ;; x)  Selectf 0 2 V t j MatchSignature( ;; PS t ( 0 )) 6= ;;g if  6=? then Update( ;; PS t ();; x)

(t) hx;; ;; ;; obs i return

Notice that the anchor(s) computed always include the best current estimate of the observable properties needed to perform the actions ( ), and an indication of which parts of the symbolic description have actually been observed (). The next section will show two examples of use of anchoring that further clarify the role of this information.

5 Examples

In this section we present two examples of anchoring with indefinite references implemented in a robotic system. The robot, a Nomad 200, uses sonars for navigation and vision data to identify objects in the environment. The two-layered decision making architecture of the robot is shown in Fig. 3.

The higher layer includes a plan generator (ETLplan), a plan executor, and a world modeler. ETLplan is a conditional planner capable of generating plans with perceptual actions and conditional branches [Karlsson, 2001]. The plan executor checks the conditions and invokes the actions in the plans generated by the planner. The world modeler maintains information about objects and places relevant for the task. It can obtain additional information about objects from the anchoring module.

The lower layer includes a navigation and a vision module. The navigation module is a simplified version of the fuzzy behavior-based controller defined in [Saffiotti et al., 1995], which executes the actions sent by the plan executor. An example of an action is (gonear A). The vision module contains vision routines for recognizing objects and for calculating properties such as color and size.

The anchoring module provides the connection between the symbols used by the planner and the world modeler, and the perceptual data provided by the vision module and used by the navigation module. It receives requests to create and update anchors and it provides the relevant information about the anchored symbols to the world modeler. It is in this module that the g function is encoded. In addition, the navigation module uses the symbols that constitute the arguments to its actions when requesting information from the anchoring module about the corresponding objects. For instance while executing the action (gonear A), it regularly requests the position of A. Finally, the anchoring module controls the vision processing, activating routines for recognizing objects and providing parameters (e.g., expected position) to focus perceptual attention.

5.1 Anchoring with partial matching

This example has the aim to show how the anchoring module works in practice and in particular the use of partial matching. It also serves to illustrate one way to handle indefinite references. The robot has the task to "find a black suitcase with a white mark and to go near it". The initial scenario is shown in Fig. 4. The largest suitcase is green, while the other three suitcases are black. The world model contains information about three objects: the two small black suitcases, identified in the world model by the symbols C (the one on the right) and B (the one on the left), and the green suitcase identified by the symbol A.

The goal given to the plan generator has the form (exists (?x) (and (suitcase ?x) (black ?x)

(white-mark?x)(near?x))), that is, the goal is to be near to a black suitcase with a white mark. The world modeler contains the information that both B and C are black suitcases, but does not have information about the mark. Therefore, the plan generator creates a plan that consists of first going near suitcase C and looking for the mark. If the mark is found, the execution stops with success. Otherwise, the robot goes near to suitcase B to look for the mark. Note that the original indefinite reference ("a black suitcase with a white mark") has now been turned onto two alternative definite references B and C. The actual plan is as follows:

((gonear C) (observe C) (if ((white-mark C . true)) (:success)) (if ((white-mark C . false)) ((gonear B) (observe B) (if ((white-mark B . true)) (:success)) (if ((white-mark B . false)) (:fail)))))

Fig. 5 (left) schematically indicates the path followed by the robot during plan execution. The robot goes first to suitcase C, checks the mark ((observe C)), does not find it, and goes to suitcase B where it successfully identifies a mark.

The navigation module, while executing (gonear C), is regularly requesting the anchoring module to keep C anchored. The latter uses the track functionality to keep track of C while the robot is moving.

The matching properties provided to the anchoring module are the properties attached to the symbol C, such as color, position, and shape, and the fact that the suitcase should have a white mark. The vision routines, due to the distance between the camera and the suitcase, cannot discriminate if there is a mark on suitcase C. A naive matching function might reject this suitcase, given that one property is not satisfied. Partial matching allows us to consider the case that the property is actually not perceivable, and the suitcase is still anchored.

A final observation is that while the robot is moving towards suitcase B, a third black suitcase, which was previously occluded, is also perceived. However, this suitcase is ignored because it does not match the perceptual signature (incl. position) of suitcase B.

5.2 Anchoring with indefinite references

This example shows the handling of indefinite references at the level of the anchoring module, as opposed to at the higher symbolic level in the previous example.

The task is to "go near a green suitcase and then go near a black suitcase". The world model contains initially two suitcases, one green denoted by the symbol A and one black denoted by B. In this case however the plan is to go near a generic object that has the properties of being a green suitcase and then to go near an object that has the properties of being a black suitcase, ((gonear x) (gonear y)). 2 The difference is that the symbols used for action now do not denote fixed specific objects, but any object in the class of objects satisfying the given matching properties. In case of x, these are black and suitcase. The positions of the two known objects are used as action properties, that is, they are used as an initial value for the gonear action. However they are not considered to be matching properties.

The path of the robot is illustrated in Fig. 5 (right). The robot first moves successfully near the green suitcase. However, when it turns towards the black suitcase, this suitcase has been removed. The robot starts moving toward the recorded position of the black suitcase, as its position was given as action property. While the robot moves, a previously occluded black suitcase is perceived: the dotted suitcase in the figure. This suitcase matches the required properties as it is black. It is therefore anchored and the robot goes near it. The fact that the position and the perceptual signature of this second black suitcase is different from those of the first one does not constitute a problem; the anchoring module just matches the percepts with the properties present in the description state, even if it uses the expected position of the first black suitcase to direct the perception and to provide information to the navigation module.

2 This plan, and the corresponding symbolic descriptors for x and y, have been created by hand, because existing planning systems only consider specific, previously known objects.

6 Discussion

The autonomous robotics and machine vision literature contains a few examples in which the need and the role of anchoring, under different names, has been explicitly identified, e.g., [Hexmoor et al., 1993], [Saffiotti et al., 1995], [Jung and Zelinsky, 2000], [Chella et al., 1998], [Bajcsy and Ko˘seck´a, 1994], [Satoh et al., 1997], [Horswill, 1997], [Wasson et al., 1999]. However, all the works above describe specific implementations and do not attempt a study of the general concept of anchoring.

To our knowledge, [Coradeschi and Saffiotti, 2000] was the first attempt to state the general anchoring problem in formal terms. The main technical contribution of this paper is the extension of the above framework with the introduction of two elements needed to deal with the anchoring of symbols in actions and plans. First we have introduced action properties, that is properties that are used in the execution of an action, but are not relevant for finding the correct object. Second, we have introduced partial matching to be able to distinguish between properties that are not satisfied and properties that are not presently available for perception, that is one cannot presently determine whether they are satisfied or not. As we consider anchoring from an action perspective we can deal with the latter case actively, for instance by observing the object from a better position. Anchoring in the presence of partial matching is actually tentative: if a property previously not observed is observed at a later point and it is discovered not to match the description, the anchor can be removed.

The problem of connecting linguistic descriptions of objects to their physical referents has been largely studied in the philosophical and linguistic tradition. These traditions provide a rich source of inspiration for the conceptualization of the anchoring problem. For instance [Russell, 1905] made a distinction between definite and indefinite references. To this respect our examples show two different ways to resolve an indefinite reference in the context of an action. In the first example, the planner resolves the indefinite reference (a black suitcase with a mark) by instantiating a variable to known matching objects in the world model, and then it uses definite references (B and C) in its actions. Note that in order to handle the appearance of a new suitcase, it would be necessary to re-plan. In the second example, the plan contains indefinite references, which are sent as such to the anchoring module. Instantiation is delegated to the anchoring module, which is able to shift "on the fly" to the new suitcase. Note that resolution of ambiguities might be more difficult in this case, without the support of the high level reasoning.

The first approach seems to be suitable for relatively static domains where there is the time to re-plan, while the second approach seems to be more appropriate in highly dynamic domains. In fact, we have used a similar approach in the Sony AIBO robots in the RoboCup competition [Saffiotti and LeBlanc, 2000]. This domain is highly dynamic, but there are few ambiguities with respect of anchoring of objects.

Acknowledgements This work was funded by the Swedish KK Foundation. We thank Lars Karlsson and Zbigniew Wasik for providing substantial help in running the robot experiments.