Decision Analysis For An Experimental Robot With Unreliable Sensors
Proceedings of the Fourth International Joint Conference on Artificial Intelligence. Robots And Productivity Technology. Pages 749-756.
© 1975 International Joint Conferences on Artificial Intelligence
Abstract
This paper reports on the continuing design of and experimentation with Jason, the Berkeley Robot. Progress has been made in various aspects of the hardware (including the chassis, communications controller, and onboard microprocessor) and software (including problem-solving programs and world models). A particular experiment, analogous to the classical "Monkey and Bananas" Problem, is described. A major feature of the reformulation of this problem is the use of Decision Analysis in coping with uncertainty. Based on the accumulated expected costs of executing the steps of various hypothetical plans, Jason can evaluate the relative merits of direct action versus prior information-gathering using potentially unreliable sensors.
- Bibliography Michael H. Smith and L. Stephen Coles, "De- sign of a Low-Cost General-Purpose Robot," Proc. of the IJCAI-73, pp. 324-335 (August 1973). IJCAI
- Alan Robb, "A Design of a Communications Con- troller for Jason, the Berkeley Robot," EECS 292H Project Report, The University of Cali- fornia at Berkeley (June 1974).
- Paul L. Sinclair and Ralph P. Sobek, "Jason Ref- erence Manual," EECS 292H Project Report, The University of California at Berkeley (June 1974).
- George W. Ernst and Allen Newell, GPS: A Case Study in Generality and Problem Solving (Academic Press, 1967).
- John H. Munson, "Robot Planning, Execution, and Monitoring in an Uncertain Environment," Proc. of the IJCAI-71, pp. 338-349 (September 1971). IJCAI
- John McCarthy, "Situations, Actions, and Causal Laws," Memo No. 2, Stanford University Artifi- cial Intelligence Project, Stanford, California (July 1963).
- L. Stephen Coles, "An Experiment in Robot Tool Using," Proc. of the IEEE Systems, Man, and Cybernetics Society International Conference (Pittsburgh, Pennsylvania, 1970).
- Drew V. McDermott, "Assimilation of New Informa- tion by a Natural Language-Understanding System," M.S. Thesis, TR-291 1 MIT Artificial Intelligence Laboratory (February 1974).
- Jerome A. Feldman and Robert A. Sproull, "Deci- sion Theory and Artificial Intelligence II: The Hungry Monkey," Technical Report No. 2 1 Computer &cience Department, University of Rochester, New York (November 1974).
- Warner North, "A Tutorial Introduction to Deci- sion Theory," IEEE Transactions on Systems Sci- ences and Cybernetics, Vol. SSC-4, No. 3, pp. pp. 200-210 (September 1968).
- Ronald A. Howard, "The Foundations of Decision Analysis," IEEE Transactions on Systems Sciences and Cybernetics, Vol. SSC-4, No. 3, pp. 211-219 (September 1968).
- Herman Chernoff and Lincoln E. Moses, Elementary Decision Theory (John Wiley and Sons, New York, 1959).
- Richard E. Fikes and Nils J. Nilsson, "STRIPS: A New Approach to the Application of Theorem Proving in Problem Solving, 11 Artificial Intelligence, Vol. 2, Nos. 3/4, pp. 189-208 (Winter 1971).
- Ramon M. Zamora and Ellen B. Leaf, "Tutorial on the Use of the SRI TREE Language System" Techni- cal Memorandum, Stanford Research Institute, ~enlo Park, California (December 1974).
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.
Introduction
As reported at the last IJCAI Conference,l the objective of our current research at the Uni versity of California at Berkeley is the design and implementation of a relatively inexpensive, general-purpose, computer-controlled, mobile robot. The Berkeley robot, dubbed Jason, was ini tially designed during the Spring of 1973 and tested off-line the following Summer. Hard-wire, blind-mode computer control was successfully ac complished during January 1974. Unreliable bread board wiring as well as greater than expected de mands for on-board power have led to a substantial redesign effort; testing of a considerably im prove~ version of Jason is now underway.
Our ultimate goal, as stated earlier, remains the investigation of the class of problems that a robot both encounters and creates while performing e lementary tasks in a real-world environment in cluding active human beings. The results of this research will hopefully enable us to construct better and safer robots at a modest price that are still capable of performing a variety of useful tasks such as factory or ware-house work or can function as a teaching aid for young children in
the classroom.
This paper is divided into five sections. The first briefly reviews some of the recent im provements to Jason hardware and software. The second section suggests some of the ways that ro botics research differs from conventional AI problem-solving research. The third section pre sents a decision analysis formulation of the clas sical "monkey and bananas" problem. The fourth section provides the results of the decision anal ysis. Finally, the last section summarizes and proposes some improvements to Jason hardware and software for the future.






FIGURE 2e JASON WlTll CONTROL TELETYPE
B. Software
On the software side, the check out of real time interactive routines was handicapped by the removal of the HP-3000 computer from the Lawrence Hall of Science. Thus, all interactive work with Jason during the last year was simulated on the CDC-6400 available on the Berkeley campus. We have recently transferred Jason software to an in teractive DEC PDP-10 computer system and have suc cessfully tested Jason over the ARPA Net.
In the mean-time the Jason simulator, which has produced output tapes capable of actually driving Jason in blind mode, has grown extensively to include a much broader collection of Intermedi ate Level Operators (ILO's) such as Move, Turn, Face, Goto, Push, Pushto, Gotodoor, Gothrudoor, etc., capable of execution in an arbitrary collec tion of rooms connected by doorways and corridors, navigating optimally through an arbitrarily com plex collection of boxes in any room. This work is documented in the Jason Reference Manual,a and although it represents the work of many individu als, two of the authors (Sinclair and Sobek) are largely responsible. Output from the simulator will be seen in Section IV.
Real-World Vs. Toy Problems
Early research in artificial intelligence tended to focus on a few well-known puzzles or "toy" problems, such as the Monkey and Bananas, Missionaries and Cannibals, or Tower of Hanoi problems (see Ref. 4 for these and other examples). Although toy problems demonstrate the intellectual competence of computers along one narrow dimension, research in robotics has broadened considerably the scope of the problem-solving enterprise. Our experience with the Jason project permits us to identify at least four general criteria which dis tinguish real-world robot problems from toy prob lems: problem-solving environment, problem formu lation, data requirements; and solution require ments.
A. Problem-Solving Environment
A rough spectrum of problem-solving environ ments in terms of increasing complexity is indi cated in the following table:
In the language of Table 1, almost all work in AI was conducted in a sterile environment (El). Subsequent early robotics research began with surgically-clean environments (E2) and was se verely criticized for giving the appearance of E3 to uneducated observers, when in reality it was not very much of an advance over El. As more ad vanced scene analysis and perceptual techniques became available, emphasis shifted to E3 and E4. With the appearance of more sophisticated hard ware sensors initial forays are being made into benevolent environments (ES). All work to date in Natural or Hostile Environments (E6,7) has been done with teleoperators, where a human is an es sential part of the loop.
B. Problem-Formulation
Because of the real-time execution and training aspect of robotics work, the problem for mulation must be accomplished in human terms rather than mathematically. Thus, voice-input, restricted natural-language-problem statements are desired. Other techniques to facilitate man machine interaction such as "joy-sticks," cursor tracking balls, or light pens are also needed.
C. Data Requirements
Information to solve the problem may either be inadequate or embedded in a large quantity of seductive but mostly superfluous data, or some combination of these. Insufficient information might occur for a variety of reasons: (i) it may not be knowable in principle, (ii) it may not be known whether it is knowable in principle, (iii) the necessary information is knowable, but the cost of acquiring it may be prohibitive. (As a special case, the cost may be reasonable, but ac quisition cannot be accomplished within suffi-. cient time to be useful), and (iv) it is not known whether the cost of information-gathering will prove to be prohibitive. (In this case de cision analysis may be useful.)
Once obtained, data may still possess uncer tainty ~r lack credibility for various reasons: (i) the data may be incorrect due to statistical unreliability in the sensory path, (ii) the source is known to be prejudiced, (iii) the source is known to be antagonistic and may deliberately pro vide false leads. Finally, (iv) the data may be inconclusive because of inherent ambiguities within the model upon which it is based and may not yield a definitive interpretation. Medical or meteoro logical data fall in this category.
| Environment | Descriotion | |
|---|---|---|
| El. | Sterile | Mathematically orecise no interaction with the real world. |
| E2. | Surgically Clean | Real-world inputs, but . highly contrived, such as painting objects with saturated colors so that the robot can identify them more easily. |
| E3. | Passive | Typical interior environment (such as an office) without people. Also, no wind or shadows due to changing illumination. |
| E4. | Active | Typical exterior environment (trees, sky, etc.), but without people or animals. |
| ES. | Benevolent | Active environment with cooperative humans exhibiting ruled behavior (such as in a factory or oarkin2 lot). |
| E6. | Natural | Benevolent environment includin2 animals as well as seasonal weather chan2es. |
| E7. | Hostile | No constraints: mines, p~tential adversaries. deep under water, outer space, etc., including |
D. Solution Requirements
As distinguished from conventional AI problem solving, a solution is not a solution for a robot until it has been successfully implemented ·as action in the real world. There are many opportu nities for failure along the path to a solution in this sense: planning failures, execution failures, and decision failures (a failure of communication between the planner and the executor).
- Planner Failures- -Within the planner various failure modes may occur: Either a plan is found or it isn't. If no plan is found, it could either be due to the fact that none exists (i.e., the task is truly impossible) or the system lacked the intelligence to find one. If a plan is found, it might still fail for a variety of reasons~ (i) it never could have worked (i.e., it fails in prin ciple); (ii) it sometimes works (i.e., it fails in practice). A plan is said to be incomplete6 (or soft) if it deliberately avoids dealing with all logically possible contingencies. Although such fragmentary plans are generally undesirable, they are sometimes preferable to no plan at all. Yet even a complete (or robust) plan will occasionally fail at some point in its capacity to sustain vari ation in environmental boundary conditions. If one were to plot the performance of a robot plan as a function of environmental complexity (El to E7 of Table 1) then one could characterize the failure mode as precipitous or capable of graceful degrada tion in proportion as whether the shape of perfor mance fell off sharply or smoothly with complexity; (iii) even though questions of optimality are rarely stated explicitly in the problem formulation because it is normally unimportant whether the ab solutely best way of doing something is proposed, plans should be penalized as failures if they are ludicrously inefficient in accomplishing the job. A plan post-processor might be useful in overcoming this kind of failure; (iv) the use of nondetermin istic plans with parallel subsolution paths may make a plan more robust at the possible expense of introducing other failure modes.
- Execution Failures--Execution failures come in two broad categories: internal and exter nal. Internal failures sometimes called crashes, can either be hard or soft. A hard crash is not immediately recoverable, and the plan must be re initialized. It may have been the result of either unreliable hardware or software. By comparison, a soft crash. usually due to a high-level monitor failure, will allow the robot to resume the plan where it left off, after a delay for reloading a fresh copy of the monitor. External failures are of three main types: (i) The robot failed, and knows that it failed. This may be due to either
systematic or random errors in its operators when executed in the real world, since all actions have inherent uncertainty in their outcomes. (Better calibration should hopefully minimize systematic errors.) There may also be other legal error modes for operators, such as "timeouts" or resource-exceeded constraints; (ii) the robot failed, and didn't know that it failed (sometimes called a missense error). This may be due to in finite looping or other errors in the flow-of control or to self-deception through imperfect sensing of the true state of affairs; (iii) the robot succeeded, but thinks that it failed (some times called a nonesense error). Illegal error messages or false alarms cause this kind of fail ure.
- Decision Failures--Decision failures are much more subtle. Five general types will be men tioned: (i) too little or too much time devoted to planning compared with execution. This depends on the amount of time spent planning, the cost of thinking, the utility of the goal, the penalty for incurring undesirable irreversible state changes in the real world, and so forth. Note that human intuition may be very poor in this regard, since most human planning appears to take place at the subconscious level and therefore creates the illu sion of being cost-free. Also, human planning and execution can frequently take place simultaneously, assuming that the execution process is not too intellectually-demanding. A robot may not always have this luxury; (ii) the failure to capitalize on serendipity. Tunnel vision during execution may cause the robot to push the solution out of the way in order to recreate the solution ac cording to plan; (iii) failure to adequately re parameterize plans based on past experience. This is sometimes referred to as structural as distin guished from statistical learning; (iv) failure to reorder priorities dynamically. Multiple, possi bly conflicting goals must be continually moni tored during execution. This may lead to seem ingly anomolous behavior from the point of view of an outside observer, but be perfectly consistent with internal objectives; (v) failure to dist i n guish local from global failures, i.e. , calling upon the planner to replan from scratch, when sal vaging the existing plan with a minor elaboration of an existing contingency branch of the current plan would be adequate, or conversely, trying all variations of a plan that was doomed to fail. In psychiatry this kind of pathology is referred to as functional fixity.
A New Formulation of the "Monkey and Bananas" Problem
The original formulation of the "Monkey and Bananas" problen#> can be stated briefly as follows :
A monkey is in a room in which a bunch of bananas are hanging from the ceiling, just out of reach. The monkey's problem, obvi ously, is to get the bananas. In the cor ner of the room is a chair. The solution decided on by the monkey is to push the chair to a location under the bananas, climb on top of the chair, and then easily reach for the bananas.
The major interest of AI researchers in this prob lem is that it is characterized by one level of in directness. That is, the solution requires an aux iliary device or tool (a chair in this case) not obviously needed at the start of the problem. In 1970 one of the authors (Coles) succeeded in formu lating a fairly straight-forward transliteration of the problem into the world of the SRI robot. 7 The role of the tool was played by a ramp that allowed Shakey to push a box off a platform onto the floor, which he would not otherwise have been able to do. Others, such as McDermott,s have sought to general ize the information-gathering aspects of the prob lem.
In a more recent paper by Feldman and Sproull9 this same problem has served as the basis for a decision-theoretic approach. Although they are much more concerned with the use of a numerical utility function during planning to develop a more efficient search strategy, we have independently reached the same conclusion regarding the positive value of joining decision analysis with a symbolic robot problem solver to facilitate intelligent de cision making under conditions of uncertainty. (See references 10-12 for an introduction to decision analysis.) In particular, using this approach we can create a decision tree that allows one to "roll back" the consequences of further information gathering operations in comparison with direct ac tion. Of course, decision analysis can never guar antee a desirable outcome; it can only provide rea sons why one course of action will in general be better than another.
Because of the inherent unreliability of Jason's ultrasonic texture/range-finder, we sought to find a realistic reformulation of the monkey and bananas problem that would also illustrate the value of decision analysis when using this sensor. Figure 3 shows an initial plan view of Jason's world. It consists of two connecting rooms, R60 and R70, containing various boxes. Jason, cur rently in R60, is designated by the symbol "J" fol lowed by an arrow indicating his principal orienta tion. The symbol "W" designates a wall, while the "+" sign indicates a clearance border for naviga tion purposes. Jason's only current goal is "IN(J,R70 1 100)," i.e., Jason desires to be in the adjoining room with a utility value of 100 ergs. Thus, the accumulated cost of all his effort (both planning and execution) i n accomplishing this goal should not exceed 100 ergs; otherwise Jason will have wasted his energy.
Now in this formulation, although "thinking" is assumed to be free of charge, every operation Jason can carry out in the real world is energy con suming . Table 2 shows the approximate cost of an application of each of the !LOs relevant to this
1 ~

FIGURE 3 PLAN VIEW OF JASON' S WORLD problem.* Note that in general they entail a sub stantial start-up cost possibly plus an amount proportional to distance moved or turned. The proportionality constant, a, is on the order of 1/10 when distance, d(x,y), is measured in feet. Also note that "pushing" is twice as expensive as "moving." The preconditions and postcondition& indicated are typical of a STRIPS-likeJ-3 symbolic problem solver.
Under normal conditions the problem solver would yield the plan: (i) test for clear path to door D67 (connecting Rooms R60 and R70), (ii) Go to Door; (iii) Go through door. This could be ac complished for about 25 ergs, making it quite an attractive plan. However, in this formulation there i s a box blocking the doorway, which would have caused "clearpath" to fail. Thus, the prob lem solver might instead generate the plan (i) Go to box; (ii) Push box (out of the way); (iii) Go to door; (iv) Go through door. This plan might executed for about 35-40 ergs, still making it - quite attractive.
However, in this particular world there is an additional complexity regarding the pushability of boxes. By definition, there are two general types of boxes: short and tall. Short boxes are not directly pushable because Jason's push bar would overhang them. Nevertheless, a short box could be pushed by means of a pushable tall box as shown in Figure 4. Furthermore, tall boxes come in two varieties : smooth and rough. Smooth boxes are
* Actual costs are accumulated by calls to Low Level Operators (LLOs) which may vary depending on the circumstances.
| Postconditions | |||||||
|---|---|---|---|---|---|---|---|
| Onerator | Description | Approximate Cost .(ergs) | Preconditions | Delete List | Primary Add List | Secondary Add List | |
| 1. | Clearpath(a) | Ultrasonic Torch deter- mines whether an obstacle blocks a straight-line path to point a. | 1 | Face(J,a) | Clearpath(a) | ||
| 2. | Texture(B,p) | - Ultrasonic Torch deter- mines whether the texture of box B is rough or smooth with probability p. | 1 | Face(J,B) IN(J,R~l) IN(B, R) | Texture(B)= Rough or Smooth | ||
| 3. | Turn(t) | Jason turns t de2rees. | 0/ J+t;st | Clear(t) Ande( J A+-S 1) | Ande(J A) | Ande(J, A+t) | |
| 4. | Hove(d) | Jason moves d feet. | J+o-d | AT(J 1 a.-.$1) Clearpath(a+d) IN(J,R+-$1) IN(J+d R) | AT(J,a) | AT(J,a+d) | |
| 5. | Go to( a) | Jason goes to point a in the same room. | 5+CYd(J,a) | IN(J,R+-$1) IN(a,R) | AT(J,$1) | AT(J,a) | |
| 6. | Gotodoor(D) | Jason goes to door D con- necting the current room to another ad joininR room. | 5-+ad(J,D) | IN(J I R+-$1) CONN(D,R,$1) | AT(J,$1) | AT(J,D) | |
| 7. | Gothrudoor(D) | Jason goes through door D. | 5 | AT(J,D) IN(J I R<-$1) CONN(D R R'..,.$1) | IN(J,R) | IN(J 1 R') | |
| 8. | Push(B,a) | Jason pushes box B to point a. | 8+20'd(B 1 a) | Pushable(B) IN(J I R+-$1) IN(B,R) IN(a,R) AT(B,b+-$1) AT(J b) | AT(B,b) AT(J,b) | AT(B,a) | AT(J,a) |
Notes: d(x,y)= distance from x to y. Ql ~ 1/10. "$1" matches a single arbitrary constituent. "x..-.$1" means that x is bound to whatever value "$1" matches.

FIGURE 4 JASON USING A TALL BOX TO PUSH A SHORT BOX pushable, while rough boxes are nonpushable (be cause they're too heavy). Now if the box blocking the doorway were tall, the preceding plan might be put into effect. However, it is known by Jason to be short. Thus, in such a case the existence of an available smooth tall box is a prerequisite to solving the problem. Now Room R60 contains not one, but two tall boxes. If Jason knew for a fact that at least one of the boxes were smooth and which one it was, the following plan might be gen erated: (i) Go to the smooth box; (ii) Push the smooth box to the low box (blocking the door); (iii) Push both boxes (out of the way); (iv) Go to door; (v) Go through door. Such a plan might be executed for about 60-70 ergs and corresponds closely to the original monkey and bananas problem. If both boxes were known to be smooth, Jason would choose to go to the box that minimized the com bined cost of going and pushing. Note that the assymetric cost of these operations would in gen eral place a premium on the box closer to the low box. Since both boxes are approximately equidis tant to both Jason and the low box, Jason is indif ferent according to this criterion.
However, in this case Jason does not know a priori Whether neither, one, or both tall boxes are smooth. The a priori probability distribution of rough and smooth tall boxes is assumed to be uni form. Jason has available through its ultrasonic range-finder, a texture operation he can perform to determine whether a box is smooth with probability p, i.e.,
Prob(smoothltexture=smooth)=p
Prob(smooth!texture=rough) =1-p
Prob(rough ltexture=smooth)=l-p.
Prob(rough ltexture=rough) =p.
Using common sense, if p is very close to 1 1 then a cost of 1 erg to measure texture is likely to be a worthwhile investment compared to the risk of going to a possibly rough box while the other one might have been smooth. On the other hand as p ap proaches 0.5, the texture operation becomes in creasingly unreliable and the marginal utility of the information obtained with respect to the cost of gathering it becomes smaller. Beyond some specified point of indifference as p approaches closer to 0.5, the cost of information gathering becomes prohibitive compared to its value. Testing texture would actually be counterproduc tive, and the best strategy would be to choose a box at random, go to it 1 and try to push it. In the worst case for Which a solution were possible, i.e., the first box tried was rough while the other was smooth, the cost might be between 80 and llO ergs, therefore still worth trying.
Now Jason has some empirical statistics on the reliability of his range finder that indicate that p=0.95. What should he do? Texture operations are expensive and risky. Yet any action may be frought with peril. Jason turns to decision analysis to provide an answer. Figure 5 shows Jason's Decision Tree for the relevant portion of this problem. The results of the analysis are presented in the next section.
Results of the Decision Analysis
The internal representation of the decision tree for evaluation purposes is as a two-page "SEETREE" programl" which is very similar in ap pearance to Fortran IV. Each node, whether a deci sion node or a probability node, is defined as a separate function with its successor designated by the identifier "NEXT." The SEETREE program is translated into a standard FORTRAN IV program by a translator package operating over the ARPA Net at UCLA. Upon execution, the system generated a 56 node tree. Table 3 shows the "selected decision" for various values of p. The system also automati cally provides rollback values of all subsequent decisions in the tree and the minimum, maximum, mean, and standard deviation of rewards for the lottery on the tree. A cumulative probability distribution of lottery values is also plotted automatically.

| D | Selected Decision | Certain Equivalence | Certain Equivalence of Alternative Decision |
|---|---|---|---|
| 0.80 | GOTO Box62 | 67.500 | 67.250 |
| 0.90 | GOTO Box62 | 67.500 | 67.500 |
| 0.95 | TEXTURE Box62 | 67.625 | 67.500 |
| 1.00 | TEXTURE Box62 | 6 7. 750 | 67.500 |
Inspection of Table 3 reveals Jason's indif ference point to be p=0.9, since the certain equiv alence for either decision is the same. Since Jason's historical data suggests a value of p=0.95 1 his optimal strategy should be to measure texture before going to either box. If the sensor reports back "smooth," then he should go iumediately to that box. Otherwise he should go directly to the other box without further measurement, since fur ther increase in the confidence of its true tex ture would not make a difference in Jason's subse quent behavior.*
* Providing p <1. Of course, if p=l and the first box was discovered to be rough, then testing the texture of the second box would be useful: if it too were rough, Jason could definitively give up without moving. However, if there is even the slightest possibility that the sensor was in er ror (p<l) 1 Jason would be compelled, lacking other alternatives, to verify a box's roughness empirically by going to it and trying to push it.
, <;t'IN4 f" lll f'lU ·I.Jf"41 .,. ·;r ·t .,, ,,,..,. ' II ''''" .. "" · .,.., 1 t ~ f'n,..fll!:ltrff" ·····' ,,,,. ... ,.,....,, ,. '"" ·~n .. ,..,, I'\ ,., ,,. .. , . f·ft WltHH l'llf' Rt'tn .. ,._f) l 'i "" P"fl"rfo f'Uiflf.ll 7 I' 4J t·, 1-"o'>lo fHif'" ·I IJTH Of!' l>llo llo"""P I'\. P"'II'P"f· , ..,, .. "'' I !I. nrtt'"'· .H"'InDIJlo" f!"o "' t · llo 11 . ... 1. ,..,. wtntu fW 1\oii'IMI #oO '', ., · .,,. f"WW"'f' l""f) ,, l"l,:t .... ' · .,,,. ,I I " illlf t·, 'llo ........ .,. ~~ "' · · ,, .... 1. ,,,.,., . I '\ illlf I ·I o 11 1. , , ,. t·fi4C.ttt ,,. "., · ..,, t'\ "" w1or,.,. nr "''·"'· t'\ · rw.rr. 1"101 11'11Gf11 ,.,.. 'tr'l.#o:O l 'i :1> ffi"'To , .. Wl llft'l, ""ll,..7 ., ",,_rt · .... ' ............... ....... , . ~.,. ,., "'· ,..., .,.,, .. ,, "'"""'' ., ,. ,,,..,. t ·H ,.,.. ,,. .... , '" 'llla""l 1 -. "· ·"· ,. .. , '. ..., , ,. ... , ,.... " "·'··' t ·, 1 ···nt · .. , .. ,,.., n· ······· , ., 1 rrnt. Tflll:" <t.Hf~ ,. t 1f" ""lf.l T'\" 1Jt "(o1Hf'>o Itt,: ....... . ,. tW ""·'·7 I' n ·II r,IJ I I " "· · 1>1,. 4NI"4 ,. ·'If" 'VI 'If I ' ' ·1 II (",PI I ··, , f ·U " LfNr.fOO Oil "llllot7tl I~ ;o ,"> f" ·f"l , t oW wtn1"H 1· .,"''·'CI ,, ""'\fOlio ,.,..W>,? I' "' tn, · 14! ... 1 · ,.....,.Ptrn '' ""' l·lto ··· · lot~ tr..C,f"H ('II" '4·la71 t'i I 1111Ho ' "'" Wl nfH ""' "nl? l I' I ~' : Jol·l, f ·4f ' 1.-ti", IOI "' llltll 'l ,._ 1 fl'll··t· l'il' "''·IIOI..f' Ill' ·· .·111 I' n oU (,t· t' '· · w1 " ' '' ,..., onnPt-rn ' ' , relft, ""·'· ,, '" .. ...... .,., . ... , ." . ·~ "' t '· ··· ' ,. s '
FIGURE 6 INITIAL AND BOUNDARY CONDITIONS

FIGURE 7 PLANl
Now, in the case where Jason goes to either the first or the second box and discovers it to be rough (i.e., non-pushable), he must then go to the alternative box in the hope that it might turn out to be smooth, regardless of what he thought it likely to be. Only if both boxes are directly proven to be rough can Jason give up with assurance.
Based on the above analysis , direct output from the Jason simulator is provided in Figures 611. Figure 6 provides a statement of the initial conditions. Conwnents are indicated between slashes. The English sentences appear just as they would be typed into the Jason terminal for interactive exe cution. They are translated into an internal grid model shown in Figure 3 by a simple natural language parser based on a precedence granwnar.
.. ,,,,..
-..n, ,., .. , ., · ·, 1
f · '1 0 ' "I, I'' I , f' · f 1?, t·l
I V'll' ·
' 1, ··" o
, ·· · · , fi t · .,



..
. . . . . . "
. .
. .

. .
FIGURE 11
Figure 7 shows the form of the plan output by the symbolic problem solver (comments inserted be tween slashes). Planl is then executed interpre tively. In this case under the assumption that the texture of Box62 is reported to be smooth and fur ther that it is actually smooth, and therefore pushable, the final cost of the plan under simu lated execution is 92.95 ergs. Since this value is within the specified utility of 100, Jason has achieved a net profit of over 7 ergs.
Figure 8 shows the initial state of R60 with the proposed trajectory marked by arrows ("+" signs have been suppressed.). In Figure 10 Jason has pushed both B61 and B62 out of the way. Finally, Figure 11 shows Jason having executed the Gotodoor/ Gothrudoor portion of his plan. In execution, this plan produced a string of 19 individual move and turn commands, each of which generates its own motor command or Low Level Operator (LLO), re sulting in a SO-page listing of grid positions. The simulated execution took approximately 3 sec onds on the CDC-6400 and 7.6 seconds on the PDP-10. Based on prior experience, we expect that actual execution in the real world will take on the order of 3 minutes.
Summary and Future Work
The major contribution of this paper is a dem onstration, by means of a well known example, of how decision analysis can be used to improve the decision-making capability of a robot under condi tions of uncertainty in its perceptual inputs. Now that Jason has been demonstrated over the ARPA Net, our next priority will be to link the decision analysis software with the Jason control software as an integrated system. We can then experiment dynamically with different boundary conditions as well as different levels of reliability for texture measurements.
In the longer term we have outlined a number of objectives. Our intermediate goals include the development of software 'to handle (i) multiple (possibly conflicting) time-dependent goals, (ii) dynamic tracking (of a cooperative agent), and (iii) dynamic real-time collision avoidance during navigation, including the evasion of active agents such as slowly moving people in a crowded corridor. Our long term goals include the application of a Jason-like robot to factory or warehouse work where the environment is fairly well controlled.
The Berkeley robot project is still in the midst of design and construction. Many devices have been designed, tested, and installed. A con siderable amount of software has been written and debugged. Other devices and programs are still in the development stage. It is planned that a fully integrated robot vehicle will again be operational in the near future. Once operational, Jason will be used as a test bed for the development of fu ture, general-purpose mobile robots with even greater sophistication and intelligence.
The authors would like to thank the Ul'part ment of Electrical Engineering and Computer Sci ences of the University of California at Berkeley for its continuing support of ~he Jason Project. I In particular, Prof. David Hodges and Mr. Leonard Baldwin of the E.E.C.S. machine shop deserve special mention. We also wish to acknowledge the assistance of Dr. Ramon Zamora of the Decision Analysis Group at Stanford Research Institute.
@inproceedings{ijcai1975p119,
title = {Decision Analysis For An Experimental Robot With Unreliable Sensors},
author = {Coles, I.},
booktitle = {Proceedings of the Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-75}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Patrick Winston and Carl Hewitt},
pages = {749--756},
year = {1975},
note = {Robots And Productivity Technology},
url = {https://ijcai.org/proceedings/1975/119},
}
TY - CPAPER TI - Decision Analysis For An Experimental Robot With Unreliable Sensors AU - Coles, I. T2 - Proceedings of the Fourth International Joint Conference on Artificial Intelligence, IJCAI-75 PB - International Joint Conferences on Artificial Intelligence PY - 1975 SP - 749 EP - 756 UR - https://ijcai.org/proceedings/1975/119 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: