Knowledge Considerations in Robotics and Distribution of Robotic Tasks
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Action and Perception. Pages 96-101.
© 1995 International Joint Conferences on Artificial Intelligence
Abstract
We develop a formal tool for representing and analyzing informational aspects of robotic tasks, based on the formal concept of 'knowledge.' Specifically, we adopt the notion of knowledge-based protocols from distributed systems, and define the notions of knowledge complexity of a robotic task and knowledge capability of a robot . The resulting formalism naturally captures previous work in the areas of robot information management, but is sufficiently rigorous and natural to allow many extensions. In this paper we show one novel application - the automated distribution of robotic tasks.
- [Brafman eta/., 1994] R . I. Brafman, J . C. Latombe, Y. Moses, and Y. Shoham. Knowledge as a tool in motion planning under uncertainty. In R. Fagin, ed- itor, Proc. 5th Conf. on Theor. Asp. of Reas. about Know ., pages 208-224.
- Morgan Kaufmann , 1994.
- [Canny, 1989] J . F . Canny. On computability of fine mo- tion plans. In Proc. of .the 1989 IEEE Int. Con f. on Rob . and Aut., pages 177-182, 1989.
- [Donald eta/., 1993] B. R . Donald, J. Jennings, and D. Rus. Information invariants for cooperating au- tonomous mobile robots. In Proc. of Int. Symp. on Robotics Research, 1993.
- [Donald, 1994] B.R. Donald. On information invariants in robotics. Artif. Intel/., 72(1):217-304, 1994.
- [Erdmann and Lozano-Perez, 1987] M. Erdmann and T . Lozano-Perez . On multiple moving robots. Al- gorithmica , 2(4) :477-521, 1987.
- [Erdmann and Mason, 1993] M. Erdmann and M.T. Mason . An exploration of sensorless manipulation . In IEEE Int. Conf. on Rob. and Aut., 1993 . .
- [Erdmann, 1994] M. Erdmann. Understanding actions and sensing by designing action-based sensors. In IEEE ICRA Workshop on Design, 1994.
- [Fagin et a/., 1995] R . Fagin, J. Y. Halpern, Y . Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, 1995.
- [Goldberg, 1993] K.Y. Goldberg. Orienting parts with- out sensors. Algorithmica, 10(2) :201-225, 1993.
- [Halpern and Moses, 1990] J. Y . Halpern andY. Moses. Knowledge and common knowledge in a distributed environment . J. ACM, 37(3):549-587, 1990.
- [Lozano-Perez, 1983] T . Lozano-Perez. Spatial plan- ning: a configuration space approach. IEEE Trans. on Camp., C-32(2) :108-120, 1983.
- [Moore, 1985] R. C . Moore. A formal theory of knowl- edge and action . In Formal Theories of the Common Sense World, 1985.
- [Rosenschein, 1985] S. J . Rosenschein. Formal theories of knowledge in AI and robotics. New Generation Camp., 3:345-357, 1985.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
The notion of computational complexity has had a pro found effect on the development of computer science. While still crude, our ability to classify different compu tational problems in terms of their complexity allows us to understand inherent difficulties in solving such prob lems. Some areas of robotics, such as motion planning, have benefited from advances in computational complex ity (e.g.,[Canny, 1989]). However, the area of robotics as a whole still lacks the analog of a Turing machine, a formal device that faithfully quantifies the difficulty of a robotic task or the capabilities of a robot. The reason for this is that usually, space and time complexity of compu tation are not the dominating factors in a robotic task. Instead, the physical embedding of robots brings to the fore issues such as sloppy controllers, imprecise sensors, and spatially separated components, all of which suggest that a good model for robotics should revolve around the notions of information and uncertainty.
We propose a framework that faithfully models the information and lack thereof inherent in robotic tasks, such as is brought about by spatial distribution and im precise sensors. In doing so we join a number of authors who have recently attempted to quantify the sensing dif ficulty of robotic tasks . [Erdmann, 1994] attempts to as sess the sensing requirements of robotics tasks in terms of what he calls abstract sensors. [Donald, 1994] devel ops formal tools that allow him, among other things, to compare and classify the sensing capabilities of dif ferent concrete sensor systems such as a radial sensor and a beacon sensor. We find this recent work inspir ing, but believe that further progress can be made by couching the analysis of informational considerations in robotic tasks in a suitable abstract language. In particu lar, we believe that the formal notion of 'knowledge' that has been proposed and studied in AI (e.g., [Moore, 1985; Rosenschein, 1985]) and distributed systems (e.g., [Fagin et al., 1995]) can serve as a basis for just such an abstrac tion. We recently showed a particular application of the formal notion of knowledge to the task of robot motion planning under uncertainty [Brafman et al., 1994]; here we propose a more ambitious application of the notion, namely as a basis for the general model of informational aspects of robots and robotic tasks. In our framework, robotic tasks can be characterized in terms of the knowl edge required to perform them, and robots can be char acterized in terms of the knowledge they can acquire. We can therefore assess the ability of a particular robot to perform a task by comparing its knowledge capabilities to the knowledge requirements of the task. One of the benefits of this formal approach and its underlying se mantics is extensibility. In particular, we are able to ex ploit this feature in the analysis of multi-robot domains. As a demonstration of this, we provide a provably correct algorithm for distributing centralized robotic protocols; roughly speaking, the algorithm accepts as input a de scription of a robotic task and a high-level description of a centralized protocol for achieving the task, and out puts a high-level description of a decentralized protocol that is guaranteed to achieve the same task.
To provide intuition, throughout the paper we will an chor the formal development in the following example. Although simple, the example embodies two important ingredients - imprecise sensing, and the need to coordi nate the action of spatially distributed actuators.
Example 1. Two horizontal, perpendicular, one dimensional robotic arms must coordinate as follows. The first arm is to push a hot object lengthwise across the table until the the second arm is able to push it sideways so that it falls into a cooling bin. The length of the table is marked in feet , from 0 thru 10 (for simplicity we ignore the horizontal coordinate). The second arm is able to push the object if it is anywhere in the region [3,7] . The second arm cannot hit the object while the object is in motion, but on the other hand the object cannot remain motionless for more than an instant or it will burn a hole into the table. Thus the second arm must move precisely when the first one stops. We consider four variants of the problem:
- la. The arms share a controller. The controller has access to a sensor reporting the position of the object with error no greater than 1, i.e., if the object's current location is q then the reading can be anywhere in [q- 1, q + 1].
- lb. Same as la, except the error bound is 4 rather than 1.
- Each arm is controlled separately. Each controller has access to a location sensor as in la; however these are two independent sensors whose readings may differ (within the allowed bounds) .
- The situation is as in lc, except that only the first controller has a sensor. However, in addition the first controller can emit (e.g., infra-red) signals, and the sec ond controller can reliably detect them.
It is not hard to see that in cases lb and lc there does not exist a protocol that will achieve the task, whereas in cases la and ld there do exist such protocols. 1 I
There are three remaining sections in the article: (2) the formal model and language, (3) an application to the distribution of robotic tasks, and ( 4) discussion of related work.
2 The model
We start by presenting our model, which is based on the notions of Abstract Robotic Domain (ARD) and Abstract Robotic Unit (ARU) . In the second section we present a (by now standard) logic for talking about the model, including the knowledge of ARUs. In the third section we introduce the new notions of knowledge capability and knowledge complexity, which we then relate to the notion of knowledge-based protocols .
2.1 Abstract Robotic Units and Domains
We start by defining the notion of an Abstract Robotic Domain, or ARD. An ARD consists of a set of possi ble states and the possible transformations among them. Roughly, a state of the ARD corresponds to the notion of configuration in robotics [Lozano-Perez, 1983] ; it en codes everything that is not internal to robots, such as the location of the robot and other objects. The informa tion and computation capabilities of a robot are captured by an Abstract Robotic Unit (ARU). An ARU is a state machine whose actions "cause" the ARD's transitions. Different ARUs acting on a given ARD have identical actuation capabilities, but their abilities to sense and compute can vary.
Definition 1 An ARDis a pair (C, T) where C, the con figuration space, is a set of states, and T , the transitions, is a set of functions from C to 2c \0, containing the iden tity function.
1 For example, the centralized protocol in case la might be as follows (r is the current reading): If r ~ 4 then (Move(arm1 ),Stop(arm2)); else (Stop(arm1 ),Move(arm2)). Similarly, a decentralized protocol in case ld might be:
Protocol for arm1: If r ~ 4 then Move; If r E [4, 6] then signal and stop. ·
Protocol for arm2 : If Signal has been detected then Move; Else stop.
An ARU over an ARD (C, T) is a triple (States, Actions, !nit), where States is the set of local states of the ARU, Actions is a set of functions from GS = C x States to 2GS \0, and I nit is a function from C to 2State·\ 0. GS is called the set of global states. We say that f E Actions implements the transition T E T if for all c, c' E C and state, state' E States it is the case that if (c', state') E f(c, state) then {1} c' E r(c); (2} if c" E r( c) then there exists some state" E States such that ( c", state") E f( c, state). The actions Actions of an ARU over ARD (C, T) must all be implementa tions of transitions in T , and must implement all such transitions.
Given a set of initial configurations I C C the set of reachable (global) states S[I] for an ARU (States, Actions, !nit) is the smallest subset of GS that contains {(c, /)lc E I and I E I nit( c)} and is closed un der Actions.
The projections of a global state ( c, /) E GS are defined ( ) def ( ) def as 1rconfig c, I = c and 7rlocal c, I = I.
We will sometimes refer to an ARU as a 'robot,' but there is no requirement that the sensors and effectors make for a contiguous piece of equipment or that they are otherwise related to one· another. For this reason it is often convenient to view an ARU as comprising of ARUt , ... ,ARUn, where ARU; =(States;, Actions;) has its own local states and actions. We refer to this special type of ARU as n-ARU and to its subcomponents as sub-ARUs. The global states of the n-ARU are thus C x States1 x · · · x Statesn, and its actions are the joint actions ofthe sub-ARUs, i.e., Actions1 x · · · x Actionsn.
Throughout this paper we assume a discrete model; specifically, we assume all state spaces to be discrete, and adopt a discrete model of time. We do so to sim plify the exposition; the generalization to continuous do mains is for the most part straightforward, though some subtleties do arise ( cf.[Brafman et al., 1994] for an ap plication of logics of knowledge in motion planning in domains that are continuous in both time and space).
Example 1 (cont.) Here are an ARD and an ARU that model the controller la:
ARD1a = ([0, 10] x {Table, Side}, {Move-length, Move-side}) where Move-length transforms (q, Table) to (q + 1, Table), with no effect otherwise or when q > 9. Move-side transforms (q, Table) to (q, Side), and does nothing elsewhere. The ini tial configuration is (O,Table).
ARU la=([O,lO],{Move( arm1 ),Stop( arm1)} x { Move( arm2), Stop(arm2)}xSense-position}, l1a), where q' E Ila(q) iff lq'-ql ~ 1. That is, the possible configurations correspond to positions of the hot object , transitions correspond to length wise or sidewise motions, and initial local states and posi tions differ by at most 1. The controller's local state consists of a position reading, and its actions are joint motions of both arms, combined with sensing. An example of an ac tion description would be: (Move( arm1) ,Stop( arm2) ,Senseposition)((q, Table), r) {((q', Table), r')l(q', Table) Move-length(q, Table) & lq'- r'l ~ 1}. This description is consistent with the fact that the position and position read ing of reachable global states can differ by at most 1. I
From now on we fix the physical characteristics of the environment, i.e., we assume a given, fixed ARD (C, T); this allows us to concentrate on epistemic considerations.
Next, we define a number of straightforward notions. A history over a set W is simply a sequence of elements of W. We define a task to be a pair of sets of configurations, which intuitively correspond to the set of initial and goal configurations. (A task can be defined more generally as an arbitrary set of histories over C, but in this paper we avoid this generality.) We say that an ARU can perform a task if it can be equipped with a controller that will lead it to a goal state from any initial configuration. To describe controllers we use the notion of a protocol (or policy), an assignment of actions to local states. Each protocol has a set of possible executions, i.e., sequences of global states that can be obtained when this protocol is followed. -
Definition 2 A history over a set W is a function
h : N----+ W, where N are the integers.
A task is a pair Task( I, G), where I, G C C.
A protocol for an ARU is a function P : States ----+ Actions.
A distributed protocol for n-ARU is a set of functions Pi : Statesi ----+ Actionsi fori= 1, ... , n.
A joint-protocol is a (centralized) protocol for an n ARU, i.e., a function from States1 x ... x Statesn to Actions1 x ... x Actionsn.
An execution of the protocol P is a history h over GS such that h(n + 1) E P(1r!ocal(h(n)))(h(n)).
A protocol P performs Task(!, G) if every execution of P that starts in {(c, /)lc E I and I E !nit( c)} passes through a configuration in G.
An ARU can perform Task(!, G) if there is a protocol for it that performs Task(!, G).
2.2 Talking about what ARUs know
The model given in the previous section provides a sta ble basis, but the real power will come from the language with which we choose to speak about the model. The following definitions are by now standard in the formal AI and distributed computing communities ( cf. [Rosen schein, 1985] and [Halpern and Moses, 1990]), but are probably new to many robotics researchers. While we include all definitions here, we will be able to provide full intuition for those new to the area only in a long version of this paper.
Assume a robotic system with a set S of reachable global states (i.e., configuration states as well as lo cal states). To be able to talk about the properties of states inS we introduce a propositional language£, con structed from a collection P of primitive propositional symbols and the boolean connectives ---, and 1\ (we re strict the article to the propositional case). This lan guage describes properties of the system's configuration, such as the robot's being in the goal. We then add an interpretation function 1r that assigns a truth value to elements in P. Given £ and 1r we define the satisfiabil ity of a formula cp E £in a state s E S, written S, s F= cp, as follows:
- S, sF= p for pEP iff 1r(s,p) =true;
· S, s F= ·cp iff it is not the case that S, s F= cp ;
· S, s F= cp 1\ '¢> iff S, sF= cp and S, s F= ?/>;
· S F= cp iff for all s E S we have that S, s F= cp .
We now augment the language with the notion of knowledge. We say that an ARU in local state I knows a wff cp if cp holds in all global states in which the ARU's local state is /. Formally:
- S, s F Kacp iff S, s' F= cp for all s' E S such that sub-ARU a's local state is identical ins and s'. 2
Example 1 (cont.) Consider variant la, and let the proposition g stand for the assertion "the object is in the goal region, i.e., in the region [3,7]." When the controller has the position reading of 4, it might in fact be in one of three actual positions: 3,4 and 5. However, since all these positions satisfy g, we can say that it knows g at this state. I
As is well known in AI and distributed systems, the properties of this definition can be captured in a small collection of axioms known as the S5 axiom system. Go ing into the properties of 85 is beyond the scope of the paper, but we do remark that these properties bear only a crude similarity to the commonsense notion of knowl edge. However, this less-than-perfect match will not make the formal notion any less useful for our purposes.
2.3 Knowledge complexity
Having defined an implementation-independent notion of knowledge, we are in a position to define a complex ity measure over robotics tasks and a capability measure for robots. We first define the capability of a robot to attain knowledge. Intuitively, for a robot to know some thing it must either already possess the knowledge, or else be able to take actions at the conclusion of which the knowledge is guaranteed. These actions may be sim ple sensing, running an internal routine, or navigating around the environment to gather information. In this article we allow only 'non-destructive' knowledge acqui sition; that is, we allow this to happen through actions that culminate in additional knowledge (and thus change in local state) to the robot, but in no change to the sys tem's configuration.
Definition 3 An ARU is K-capable of {cpo, ... , cpk} C £ in a set of global states S if there exists a protocol P such that for every s E S, every execution of P that starts at s reaches a state s' such that (a) S, s' F= K cpo V · · · V K 'Pk, (b) s and s' differ at most in the local state ofthe ARU, and (c) the ARU knows that (b) holds. 3
The knowledge-capability of a robot is characterized by a set of propositions, the interpretation of which is that the robot can come to know at least one of those at each configuration. This definition embodies the notion that sensing is nondeterministic. The robot may be able to guarantee that it come to know one of several facts, but not any one of them in particular . For example, given a position sensor with ±1 error, sensing the posi tion when in location 4 will yield knowledge of one of the following three facts: "the location is in the 2-4 region," "the location is in the 3-5 region," and "the location is in the 4-6 region ." Yet, knowledge of any one particular statement is not guaranteed.
2 We use a subscripted K to distinguish between the knowledge of different sub-ARUs. This will also allow us to make statements such as 'sub-ARU a knows that sub-ARU b knows cp': KaKb'P· When the the ARU is obvious from the context we will drop the subscript, as in K cp.
3 This is a subtle point which will be discussed in a longer version of this paper. We briefly mention that (b) and (c) always hold when we restrict P to purely sensory actions, i.e., actions that never change the configuration. Alternatively, (c) can be handled by crafting a class of protocols with an explicit termination condition.
Definition 4 { <po, ... , <pk} is an upper bound on the K complexity of a task Task( I, G), written Task(!, G) = O({<p0 , ... ,<pk}), if {1} any ARU that is K-capable of {<po, ... , <pk} in S[I] can perform Task(!, G); {2} Some ARU is K-capab/e of {<po, ... , <pk} in S[I].
The notion of a lower bound can be defined similarly, but it does not play a role in the sequel.
We make two observations about K-complexity. First, it differs from the notions of time and space complex ity in that K-complexity values are not totally ordered. Second, there appears to be an interaction between K complexity on the one hand and time and space complex ity on the other . Intuitively, while a robot with minimal knowledge might be able to perform a task, with more knowledge it might be able to perform the task more ef ficiently in terms of computation time or space. We do not explore this interesting tradeoff here, but we believe it represents an important issue.
Example 1 (cont.) Consider variants la and lb. Recall that in both variants a central controller is in charge of a two armed robot, which must perform two actions simultaneously when the object is in the goal region G = {3, 4, 5, 6, 7} .
K-complexity: It is easy to see that this task is 0( {g, ·g} ). However, this is not a tight bound. If in positions 3 or 4 the robot is not sure where it is, it can still man age, as long as it is able to detect the goal later. We can therefore tighten the bound to 0( {g, cp} ), where cp de notes being in {1, 2, 3, 4, 6, 7, 8, 9, 10}. That is, in G \ {1, 2, 3, 4, 6, 7, 8, 9, 10} the robot must know that it is in the goal; in {1, 2, 3, 4, 6, 7, 8, 9, 10} \ G it must know cp, and in G n {1, 2, 3, 4, 6, 7, 8, 9, 10} it should know either one.
K-capability in 1a: The first controller's sensor has an error bound of 1. To verify that it is K-capable of {g, cp} we must see that it always satisfies Kg V K cp . This is easily verified. For example, in position 3, its possible readings are 2, 3, 4, each of which makes it know g or cp. We conclude that this controller can perform this task.
K-capability in 1 b: The second controller's sensor has an error bound of 4. Given this error bound it cannot satisfy Kg at any state. g, or a stronger formula, must appear in any K complexity bound of this task, since any protocol that allows Move(arm2 ) at a point that does not satisfy g will fail . We conclude that this controller cannot perform the task. I
2.4 Knowledge-based protocols
Work in distributed systems has demonstrated that the formal notion of knowledge is a powerful tool for analyz ing traditional protocols. However, it was recently noted that the notion could be useful for design purposes too; it allows one to design high-level protocols that concentrate on the informational aspects of the task without drown ing in implementation details. We define a slight variant of an abstract notion of protocol - knowledge-based protocols (KBP), due to [Fagin· et al., 1995]. 4 A KBP is a (possibly partial) function from the set of knowledge states to the transitions of the given ARD. It can be viewed as a big case statement, each condition of which is a test on the knowledge of the ARU. The interpreta tion of this protocol is that the ARU always performs an action that implements the transition corresponding to the earliest condition satisfied. A KBP can also be rep resented in disjoint form, in which this priority is made explicit. Here are these two forms:
| KB-protocol | KB-protocol in disjoint form: |
|---|---|
| Case: | Case: |
| Ka1 r1; | Ka1 r1; |
| Ka2 r2; | Ka21\ •Ka1 r2; |
We refer to I< a 1, ... , I< an as the (knowledge) conditions of this KBP. We say that an ARU can run a KBP with conditions I<a1, ... , I< an in S, if SF Vi=l, ... ,n Ka; . Thus, a KBP specifies what to do and a class of ARUs that are capable of following this specification. This last point is an important difference between our definition and that of [Fagin et al., 1995]. Their KBPs contain a final ELSE clause, and are thus executable by any ARU.
In principle, there is always a well-defined translation from a standard protocol to an equivalent KBP. A stan dard protocol can be viewed as a special case of a KBP, since, by definition, an ARU always knows its local state. Conversely, a standard translation of a KBP P for an ARU a.nd a set of global states S is obtained as follows: Let K <p be the earliest condition in P that is satisfied in the local state I, and let r be the corresponding transi tion in P. A standard translation assigns to I an action that implements T. This translation results in a com plete protocol (i.e., one in which an action is assigned to every state) when the ARU can run the KBP in S. In the sequel we are only interested in KBPs that can be run by some ARU in an appropriate set of global states.
Informally, we say that h is an execution of a KBP if it is an execution of some standard translation of it. Formally, the executions of a KBP P from initial con figurations I C C are those executions h of a standard protocol P, by an ARU such that: (1) h(O) E {(c, l)Jc E I and IE Init(c)}, (2) the ARU can run Pin S[I), (3) P , is a standard translation of P for this ARU and S[ I). We say that KBP P performs Task(!, G) if all its ex ecutions from initial configurations in I pass through a configuration in G, and if the set of executions from I is not empty.
Notice that an assignment of the identity transition by a KBP is redundant (except in goal states) since it does not change the configuration. We therefore ignore such KBPs in the sequel.
The following lemma requires an additional definition: <pis about C iffor all s, s' E S: if 1rconfig(s) = 1rconfig(s') then S, s F= <p {::} S, s' F= <p.
4 The similarity in names between KBPs and knowledge based (or expert) systems in AI is coincidental.
a KBP with conditions ]( cp1 , ... , ]( 'Pk that performs Task( I, G) .
This lemma suggests a method for analyzing a robot 's ability to perform a task in terms of two subproblems: (1) finding a KBP P that performs the task, and (2) showing that the robot is K-capable of { cp1 , ... , 'Pn}, where I< 'Pl, ... , ]( 'Pn are the knowledge conditions of P. This robot can then perform the task by running a KBP derived from P by adding a final else clause which (abstractly) states:
Else learn whether cp1 or ... or 'Pn.
Thus, the robot will alternately be making direct "phys ical" progress toward the goal state and attaining the knowledge required to make such progress.
We conclude the section with two remarks on KBPs. First, although, as we have just mentioned, a standard protocol can always be viewed as a special case of a KBP, it is a degenerate case. KBPs are powerful precisely be cause they allow us to abstract away the idiosyncrasies of local state. Thus, for example, rather than discuss the content of the frame buffer of a robot's vision sys tem, a KBP allows us to talk about the robot knowing that there is an obstacle in front of it. Second, while in principle well defined, in practice it can be quite difficult to transform a KBP to a standard one. We believe, how ever, that, as has been the case in distributed systems, starting with knowledge-oriented analysis and design is a useful methodology.
Example 1 (cont.) Let g and cp be as defined before. Here is an example of a distributed KBP for the task, which we derive algorithmically in Section 3:
Protocol for arm1: if K1g then Stop; if K1cp then Move.
Protocol for arm2: if K2K1g then Move; if K2(K1 cp 1\ ~K1 g) then Stop.
As we will see, the use of nested knowledge operators is a natural and concise way of capturing coordination. I
3 Automated distribution of robotic tasks
So far we have provided a rigorous framework for rep resenting and reasoning about informational aspects of robots and robotic tasks. Certainly, a minimal require ment from any formal framework is that one be able to use it to reason about simple and intuitively well under stood examples; indeed, all along we have applied the framework to such an example. However, for the frame work to be something other than an idle exercise, it must ultimately be used for other than merely formalizing the obvious. One direction to go would be to increase the complexity of the robotic task until its solution or lack thereof are no longer obvious. However, here we offer a different novel contribution - a provably correct algo rithm for distributing robotic tasks; that is, an algorithm that (roughly speaking) accepts a multi-robot task and a central controller for the robots that achieves it, and out puts local controllers for each of the robots that jointly achieve the same task .
Our approach to task distribution rests on capturing the notion of centralization through the formal notion of knowledge. With central control all knowledge of the various components resides at one place, the controller.
This has far-reaching consequences. For example, in a two-armed robot, a central controller means that not only do both arms always have the same knowledge, but they each know that they do , they each know that they each know, and so on; this is called common knowledge in the logic literature. Endowing the two arms with separate controllers breaks this common knowledge; the arms may have different knowledge, or may have the same knowledge without knowing that they do. Our knowledge-level language allows us to identify the levels of knowledge required of different parts of the system, and thus to precisely quantify various degrees of central ization.
Recall that our formal language C allows nesting of the knowledge operator. For example, the sentence K 1K 2 cp reads "ARU 1 knows that ARU 2 knows that cp is the case." Recalling that "knowledge" is merely a way of capturing a certain correlation between an ARU's lo cal state and the global state of the system, this means that the above statement concisely and elegantly cap tures a complicated relationship between the local state of ARU 1, the local state of ARU 2, and the system's configuration. Knowledge operators can be nested more deeply, encoding even more complex relationships be tween states; /(2J(l/(2cp is perfectly legal.
Before describing our algorithm we must explain the notion of a progress measure, which originates in the pro gram verification and synthesis literature. The general idea is to assign values to states from some well-ordered set (i.e., a set whose every subset has a minimal element) with the goal state assigned the minimal value. Given a progress measure we can prove that a protocol performs a task by showing that each transition the protocol takes produces a new state whose value is smaller than that of the previous state. [Erdmann, 1994] ingeniously employs these ideas to the problem of generating minimal sensors. He uses an existing protocol to generate a progress mea sure that assigns to each state the maximal number of steps that the protocol might take to achieve the goal. He then uses this progress measure to obtain sufficient sensing requirements for a task. We use his method as a "subroutine" in the algorithm.
Definition 5 A progress measure for an ARD (C, T) is a function p(C)-+ W, where W is a well-ordered set.
We can construct a progress measure given a protocol and a task. The idea is to see for each state what is the longest the protocol might take to lead the system to a goal state.
Definition 6 Given a task Task(!, G) and a KBP P, the function PeP ,Ta$k(I,G)) is defined for each c E C as the least upper bound on the number of steps along any execution of P from initial configuration { c} until the first time a configuration in G is reached, or as oo if no such upper bound exists or if a configuration is reached on which P is undefined. We say that r E T makes progress oncE C according top if for any c' E T(c)(c) , p(c') < p(c).
Lemma 2 P(P,ra 8 k(I,G)) is a progress measure.
We will also need the following:
Definition 7 Given a joint KBP P for an n-ARU 1 the ith projection ofP is a KBP for ARU; containing a pair of the form "if K;cp then do T;'' whenever P contains "if K cp then do ( T1 , .. . , T; 1 ·· · , TN)" .
A configuration c possibly satisfies cp if there is an ARU 1 a set of global states S C GS 1 and some s E S such that S, s f= cp and 1rconfig(s) = c. We say that conditions cp and 1jJ are consistent (for ARD (C 1 T)) if there exists a configuration that possibly satisfies cp 1\ 1/J .
We are now ready to present the algorithm. The idea behind it is as follows. It takes as its input a task de scription and a joint KBP for n-ARU 1 and uses them to generate a progress measure over the configuration space of the ARD. It also (nondeterministically) assigns an ordering to the sub-ARUs. Next, it assigns to each sub-ARU its projection of the original joint protocol. It then sequentially goes through the sub-ARUs' protocols one at a time, adding to each just those additional knowl edge conditions needed to ensure coordination with the preceding sub-ARUs.
Knowledge-Based Distribution Algorithm
Input: (1) A task Task(! , G) (2) A Jomt KBP P for n ARU in disjoint form.
Output : distributed KBP for n-ARU.
- Construct the progress measure PeP ,Ta·k(I ,G))"
- Nondeterministically select an ordering over {1, .. . , n} .
- Project P to each sub-ARU. Call the initial protocol of ARUk , Pk .
- Let r = 2. Repeat the following until r = N:
- (a) Repeat sequentially for all knowledge condi tions appearing in p r .
- Let cp be the current condition examined; let Tr be the transition assigned to cp by p r .
- Set C = false
- Repeat for all (r - 1)-tuples of transitions T1, . .. ,Tr-1 that · ARU1, ... ,ARUr-1 may perform under conditions consistent with cp .
- If there exist transitions Tr+1, ... , Tn such that T; (where r < i < n) is assigned to· ARU; under a condi tion consistent with cp , and such that ( T1, . .. , Tr, .. . , TN) makes progress ( ac cording to P(P ,Ta·k(I ,G))) on all configu rations in Cp,I,G that possibly satisfy cp, then set C to
where 8; is the knowledge condition in P; under which T; is performed.
- tv. Replace the condition "cp then do T" in r's protocol by:
- (b) Collect conditions corresponding to the same transition (i.e., replace "Kr1/J then do T" and "Kr1/J' then doT" by "Kr(1/J V 1/J') then doT) ."
Theorem 1 Let P be a joint KBP with a finite number of executions from I and with conditions { K cp; ji E A} 1 where all cp; (i E A) are about C in S[I]. P performs the input task Task( I, G) iff the distributed KBP generated by the algorithm performs Task(!, G).
Several comments about the algonthm. First, differ ent orders on the sub-ARUs will result in different dis tributed protocols. Roughly, the later a sub-ARU is in the ordering, the more it has to know, since it must co ordinate its actions with the sub-ARU preceding it . Al though we do not have a way of quantifying the 'ease' of each distribution, some ordering may result in require ments that are easier to achieve in practice than others. Second, the output of the algorithm is highly sensitive to the input task. A joint protocol usually embodies much more knowledge (i.e., coordination) than is actu ally needed for any given task. Our algorithm uses the progress measure, and hence the task, to determine just how much knowledge to add to each sub-ARU. Finally, an implicit assumption is that the change to a distributed protocol does not affect the function !nit.
The distributed protocol we obtain is not necessarily minimal in its knowledge requirements and its proper ties, as well as those of other possible algorithms, deserve further investigation. However, it does offer a method for obtaining non-trivial specification of sufficient conditions for task distribution; these are the knowledge conditions of the distributed KBP obtained as its output .
Example 1 (cont.) The discussion in the previous section suggests the following KBP for our task: If Kg (Stop( arml),Move( arm2) ); if K cp (Move( arml),Stop( arm2)) where the proposition g and cp are defined as before.
Distribution. We start by running the algorithm on this pro tocol and the given task. We skip the construction of the progress measure, which is straightforward. After perform ing the first three steps we have:
Protocol for arm1: If K1g Stop; If K1 cp 1\ -.Klg Move.
Protocol for arm2: If K2g Move; If K2cp 1\ -.K2g Stop.
Step 4 calls for revising arm2 's protocol. The first condi tion there is Kg, and both actions Stop and Move could be performed by arm1 under this condition, since positions 3 and 4 satisfy both g and cp. The only action by arm1 that makes progress when arm2 does Move, is Stop. Stop is performed by arm1 under the condition K 1g. Therefore, we must re place K2g with K2g 1\ K2K1g, which is equivalent to K2K1g. Similarly, when we examine the action Stop, performed un der the condition K cp, we find that it makes progress only when joined with Move. Therefore, we substitute the action K2(K1cp 1\ -.K1g) for K2cp . We obtain:
Protocol for arm1: If K1g Stop; If K1 cp 1\ -.K1g Move.
Protocol for arm2: If K2K1g Move; If K2(K1cp 1\ -.K1g) Stop.
Sensitivity of distribution to task. Consider the task of Exam ple 1, but now the table is heat-resistant, so that the second arm need not start moving precisely ·when the first one has stopped, and in addition, the second arm may hit the ob ject while still in motion. Clearly the above distributed KBP will do, since the original task is more stringent than this one, but the reader may verify that, as a result of the optimization performed by the algorithm, we obtain the following KBP:
Protocol for arm1 : If K1g Stop; If K1 cp 1\ -.K1g Move. Protocol for arm2 : If K2g Move; If K2cp 1\ -.K2g Stop.
Sensitivity of distribution to the ordering of ARUs. We men tioned that the ordering of ARUs can make a difference. If arm2 was given higher priority than arm1 , we would have obtained the symmetric protocol:
Protocol for arm1: If K1K2g Move; If K1(K2<p 1\ ·K2g) Stop.
Protocol for arm2: If K2g Stop; If K2<p 1\ ·K2g Move.
In a precise sense, which we do not have space to explain, both distributions embody the same amount of knowledge. However, from the pragmatic point of view one protocol might be vastly superior to another. For example, in some situations it may be easier to detect goal configurations from a distance. In that case the second protocol may be more appropriate, since detecting g would be easier for arm2.
4 Discussion
This paper makes two main contributions:
- We present a formal model of robotics domains, a logical language for reasoning about the model, and define natural measures of the information complex ity of robotics tasks and the informational abilities of robots based on the notion of knowledge.
- We use the model and the language to provide a distribution algorithm for knowledge-based robotic protocols.
Information, and more specifically sensing, are issues of central importance in robotics. The unreliability of sensors and the difficulty in reasoning about sensory in formation has lead some researchers to attempt to reduce the sensing requirements of tasks (e.g.,[Erdmann and Mason, 1993; Goldberg, 1993]. More generally, there has been increasing interest in understanding the inherent sensing requirements of a task. [Erdmann, 1994] is one such effort which has had major influence on our work. Erdmann argues that sensors should be constructed to provide sufficient information to choose an action that makes progress. He uses progress measures, discussed earlier, to do so. Erdmann also talks about knowledge, and the semantics of his notion of information is very similar to the standard semantics of knowledge which we use. One contribution of our work is to supply a formal language that captures these ideas, which (as we have shown) has natural extensions.
Another influential idea is Donald's notion of informa tion invariants [Donald, 1994], in which 'reductions' play an important part. Roughly speaking, system A can be reduced to system B if we can use system B to obtain the same information that system A can obtain. In a longer version of this paper we discuss a natural notion of knowledge-based reduction that arises in our work, and tie it in with Donald's work. 5
Motivating our investigation of task distribution was the work of [Donald et a/., 1993]. This work exam ines distribution of manipulation tasks, starting from a centralized protocol. Their analysis of the information needed there shows that it pertains to the configuration of the manipulating robot w.r.t. the manipulated object. Using our terminology, we can say that from their work it can be concluded that these tasks do not require two levels of knowledge for their distribution (i.e., one robot does not need to know the state of the other). They are then able to obtain an asynchronous distributed protocol for such problems.
5 Updated versions of this work appear in URL http:/ /robotics.stanford.edu/users/brafman/bio.html
Finally, the use of prioritization in multi-robot envi ronments appears in a different context in [Erdmann and Lozano-Perez, 1987]. There, prioritization is used to pro duce motion plans for multiple moving objects.
We believe that the marriage of knowledge represen tation and robotics is an extremely promising direction, which we intend to pursue.
Acknowledgment: We are grateful to Bruce Donald for numerous insightful discussions and comments, to Joe Halpern for many important suggestions and correc tions, and to Nir Friedman for comments on previous drafts. This work was partially supported by AFOSR and NSF grants AF F49620-92-J-0547 and IRI-9220645.
@inproceedings{ijcai1995p13,
title = {Knowledge Considerations in Robotics and Distribution of Robotic Tasks},
author = {Brafman, Ronen I. and Shoham, Yoav},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {96--101},
year = {1995},
note = {Action and Perception},
url = {https://ijcai.org/proceedings/1995/13},
}
TY - CPAPER TI - Knowledge Considerations in Robotics and Distribution of Robotic Tasks AU - Brafman, Ronen I. AU - Shoham, Yoav T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 96 EP - 101 UR - https://ijcai.org/proceedings/1995/13 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: