A dissertation submitted to the department of computer science and the committee on graduate studies



Download 1.35 Mb.
Page1/16
Date25.05.2016
Size1.35 Mb.
#68084
  1   2   3   4   5   6   7   8   9   ...   16
DECIDING WHETHER TO PLAN TO REACT

A DISSERTATION

SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE

AND THE COMMITTEE ON GRADUATE STUDIES

OF STANFORD UNIVERSITY

IN PARTIAL FULFILLMENT OF THE REQUIREMENTS

FOR THE DEGREE OF

DOCTOR OF PHILOSOPHY

Vlad Grigore Dabija
December 1993

© Copyright 1993 by Vlad G. Dabija.

All Rights Reserved.

I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy.


______________________________

Barbara Hayes-Roth

(Principal Adviser)

I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy.

______________________________

Jean-Claude Latombe

(Co-Adviser)

I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy.

______________________________

David M. Gaba

I certify that I have read this dissertation and that in my opinion it is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy.


______________________________

Oussama Khatib

Approved for the University Committee on Graduate Studies:


______________________________




Abstract

Intelligent agents that operate in real-world real-time environments have limited resources. An agent must take these limitations into account when deciding which of two control modes - planning versus reaction - should control its behavior in a given situation. The main goal of this thesis is to develop a framework that allows a resource-bounded agent to decide at planning time which control mode to adopt for anticipated possible run-time contingencies. Using our framework, the agent: (a) analyzes a complete (conditional) plan for achieving a particular goal; (b) decides which of the anticipated contingencies require and allow for preparation of reactive responses at planning time; and (c) enhances the plan with prepared reactions for critical contingencies, while maintaining the size of the plan, the planning and response times, and the use of all other critical resources of the agent within task-specific limits. For a given contingency, the decision to plan or react is based on the characteristics of the contingency, the associated reactive response, and the situation itself. Contingencies that may occur in the same situation compete for reactive response preparation because of the agent's limited resources. The thesis also proposes a knowledge representation formalism to facilitate the acquisition and maintenance of knowledge involved in this decision process. We also show how the proposed framework can be adapted for the problem of deciding, for a given contingency, whether to prepare a special branch in the conditional plan under development or to leave the contingency for opportunistic treatment at execution time. We make a theoretical analysis of the properties of our framework and then demonstrate them experimentally. We also show experimentally that this framework can simulate several different styles of human reactive behaviors described in the literature and, therefore, can be useful as a basis for describing and contrasting such behaviors. Finally we demonstrate that the framework can be applied in a challenging real domain. That is: (a) the knowledge and data needed for the decision making within our framework exist and can be acquired from experts, and (b) the behavior of an agent that uses our framework improves according to response time, reliability and resource utilization criteria.




Acknowledgements

I would like to thank my adviser Barbara Hayes-Roth for her significant support and guidance throughout my three years here at Stanford. Through many long discussions, Barbara helped me clarify my thoughts. She has always challenged my ideas in constructive ways and often provided alternative suggestions and views from different perspectives. Most significantly, she always challenged me to look for more general solutions or more meaningful results in my research. She taught me important lessons on how to validate my work and how to present it. I have always appreciated Barbara's availability when I needed her advice most; on so many occasions she found the time to see and advise me with very little or no notice at all. Last but not least, she suggested lots of tips on how I can give my daughter a better education.

I would like to thank my co-adviser Jean-Claude Latombe for his advice, both while supervising my research and during the time I was his teaching assistant. His thought-provoking questions and perspective were very helpful in enlarging the scope of my research. I am indebted to Jean-Claude for the significant time pressure he exerted on me to complete my thesis during 1993, without which it could have taken me much more time to complete this research.

I was very lucky to benefit from the advice and medical expertise of Dave Gaba during my work here. I thank him for his patience and the time he took to supply me with expert data and to give me his feedback on my experimental results. In numerous occasions he commented extensively on my ideas from his perspective both as an expert in anesthesiology and an expert pilot. His computer science oriented comments were very helpful in crystallizing many ideas of my work.

I would like to thank Oussama Khatib for his advice on my work. He has pointed out related problems to my initial ideas, and challenged me to work out solutions to them.

Serdar Uckun has provided me repeatedly with expert data in both medical and car driving domains. I have also benefited from numerous discussions with him regarding my thesis or parts of it as well as other related topics. I want to thank him for all his time and efforts.

I have had innumerable discussions with my office mate David Ash on a huge variety of subjects, related or not to this thesis. He was always a step ahead of me in completing his Ph.D. program, and has always been a tough act to follow. The fact that we had our oral examinations in the same day was probably no coincidence. He has also provided me with a detailed description of his reactive planner model, which I have used in some of my experiments.

I would like to thank to all the experts who have helped me with their expertise in the domains in which I have conducted my experiments: David Gaba, Serdar Uckun, David Ash, Alex Brousilovsky, Lee Brownston, Janet Murdock, Rich Washington and Michael Wolverton. They have not only provided the domain data needed for the framework, but they have also evaluated the system's performance.

My work has also benefited from numerous discussions with: Lee Brownston, John Drakopoulos, Mike Hollander, Philippe Lalanda, Jan Eric Larsson, Alex Macalalad, Philippe Morignot, Janet Murdock, Marcel Schoppers, Evangelos Simoudis, Henny Sipma, Rich Washington, Michael Wolverton. They have all contributed on many occasions their comments and advice.

I would like to thank Ed Feigenbaum, Rich Fikes and Bob Engelmore for supporting my work at the Knowledge Systems Laboratory. My thanks also go towards the administrative team of KSL: Grace Smith, Peche Turner and Michelle Perrie, for a wonderful job which has made any bureaucracy related things unknown to me.

Two other groups of people have given me wonderful opportunities during my years at Stanford, and I want to thank them here. Dr. Shogo Nishida and Dr. Katsuhiko Tsujino gave me the opportunity to spend three wonderful months in their research group at the Mitsubishi Central Research Laboratory in Japan. Largely due to them, my work there was extremely productive, and my touristic experience was unforgettable. My visit there was the beginning of a wonderful friendship with them. Prof. G. Schweitzer and Nadine Tschichold-GŸrman gave me a similar opportunity in Switzerland, and I would like to thank them as well.

I would also like to thank Ranan Banerji and Val Breazu-Tannen for their support and encouragement, as well as their unlimited confidence in my abilities. Their support made this entire endeavor possible.

Financial support for my work was provided by ARPA Grant NASA NAG 2-581: Intelligent Systems for Science and Engineering Applications.

Finally, I would like to thank my parents, Antoaneta and Constantin, for their love, sacrifice and support in everything I have ever done, and for encouraging me to pursue my studies. The pride they derived from my work has given me the strength to complete this thesis. I wish to thank my two years old daughter Dominique (born between the theory and the AI comprehensive exams) for being such a wonderful child and for the beautiful moments she gave me, which have recharged my batteries many times during my work on this thesis. Last but by no means least, I want to thank my best friend and wife Tatiana for her infinite patience during the long hours I put into this work. She gave me the opportunity to begin this work and then supported me all along the way. She provided me with unlimited love and support and the right balance of encouragement and restrain to keep me going through the most difficult moments. It is to these four wonderful people that I affectionately dedicate this dissertation.

To: Toni, Puiu, Tatiana and Dominique.
Table of Contents

1. Introduction ............................................................................... 1

2. The Problem ................................................................................ 11

2.1. Contingencies ......................................................................... 11

2.2. Summary of the Problem ................................................. 15

2.3. Application Domains .......................................................... 20

2.4. Review of Related Work ................................................... 25

3. The Approach ............................................................................ 32

3.1. Intuitive Solution ................................................................ 35

3.2. Framework for Reaction Decision ... ............................ 40

3.2.1. Overview of the Framework ............................................ 40

3.2.2. Situation Space .................................................................. 44

3.2.3. Criticality Space ................................................................ 48

3.2.4. Reactive Plan Space .......................................................... 52

3.2.5. Summary of Framework .................................................. 54

3.3. Establishing the Value of Reaction ............................... 59

3.3.1. Expert Model ....................................................................... 60

3.3.2. Value of Reaction .............................................................. 63

3.4. The Reaction Decision Making ........................................ 66

3.4.1. Reactive Planner Model ................................................... 66

3.4.2. Agent Model ....................................................................... 71

3.4.3. Deciding Whether to Prepare to React .......................... 72

3.5 Conditional Planning ........................................................... 78

3.5.1. Contingencies Revisited .................................................. 79

3.5.2. Framework for Conditional Planning Decision ........... 85

3.5.3. Establishing the Conditional Planning Value ............. 89

3.5.4. Deciding Whether to Plan a Conditional Branch ........ 93

4. Knowledge Representation Formalism .................... 100

4.1. Description Languages ....................................................... 101

4.2. Example ................................................................................... 105

5. Theoretical Analysis ............................................................. 113

5.1. Assumptions .......................................................................... 114

5.2. Necessity ................................................................................. 115

5.3. Consistency ............................................................................. 120

5.4. Optimality ............................................................................... 125

6. Demonstrations ........................................................................ 128

6.1. The Driving Domain ............................................................ 129

6.2 Optimality ............................................................................... 133

6.3. Behavior Models .................................................................. 139

6.4. Complex Real World Domain ........................................... 148

7. Conclusions .................................................................................. 154

7.1. Summary ................................................................................. 154

7.2 Future Work ........................................................................... 155

Appendix 1. System Architecture ................................... 159

Appendix 2. Knowledge Representation in the

Car-Driving Domain .............................. 162

Appendix 3. Anesthesiology Domain

Experiments .................................................. 173

Appendix 4. Intensive Care Domain

Experiments .................................................. 181

References ......................................................................................... 192

List of Tables

3.1. Set of contingencies for the car driving domain ...................... 36

6.1. Contingencies for the car driving domain experiments ......... 129

6.2. Data values for the car driving domain experiments ............... 132

6.3. Criticality values for the "normal" behavior model, for the

car driving domain experiments ..................... 134

6.4. Optimality demonstrations results for reactive planner

model RP1 ............................................................. 136

6.5. Optimality demonstrations results for reactive planner

model RP2 ............................................................. 136

6.6. Optimality demonstrations results for reactive planner

model RP3 ............................................................. 137

6.7. Optimality demonstrations results for reactive planner

model RP4 ............................................................. 137

6.8 Representing Behavior Models ...................................................... 141

6.9 Reactive Behavior Experiments for the Driving Domain........... 143

6.10. Selected Contingencies for kp = 0.5 (30 seconds) for

Explorer (kt = 1.166) ............................................ 149

6.11. Selected Contingencies for kp = 0.5 (30 seconds) for

SPARC10 (kt = 1.02) .............................................. 150

6.12. Selected Contingencies for kp = 0.6 (36 seconds) for

Explorer (kt = 1.166) ............................................ 151

6.13. Selected Contingencies for kp = 0.6 (36 seconds) for

SPARC10 (kt = 1.02) .............................................. 152

A3.1. Contingencies for the anesthesia domain experiments ........ 174

A3.2. Data values for the anesthesiology domain experiments ...... 175

A3.3. Criticality values for the "normal" behavior model, for the

anesthesiology domain experiments ............... 176

A3.4 Representing Behavior Models ................................................... 177

A3.5 Reactive Behavior Experiments for Anesthesiology ............... 177

A4.1 Contingencies for the ICU domain .............................................. 181

A4.2. ICU domain contingencies ordered by criticality

for Tmin = 0.5 (2 hours) and Lmin = 1 ............. 183

A4.3. ICU domain contingencies ordered by criticality

for Tmin = 0.5 (2 hours) and Lmin = 2 ............. 185

A4.4. ICU domain contingencies ordered by criticality

for Tmin = 2 (30 minutes) and Lmin = 1 .......... 187

A4.5. ICU domain contingencies ordered by criticality

for Tmin = 12 (5 minutes) and Lmin = 1 .......... 189


List of Illustrations

2.1. Conditional plan ............................................................................... 12

3.1. Types of plans ................................................................................... 33

3.2. Overview of the Framework ........................................................... 41

3.3. The General Framework ................................................................. 43

3.4. The Situation Space .......................................................................... 47

3.5 The Criticality Space ......................................................................... 51

3.6. Reactive Plan Characteristics Space ............................................ 52

3.7. The Plan-to-React Decision Framework ...................................... 55

3.8. Functional Relationships for the Plan-to-React Decision

Framework .................................................................................. 56

3.9. Example for the driving domain ................................................... 57

3.10. Example for the anesthesia domain ............................................ 58

3.11. The Reaction Decision Making Phase ........................................ 67

3.12. Two reactive plan models ............................................................. 68

3.13. Reaction decision making algorithm ......................................... 75

3.14. Contingency space - linear representation ............................. 81

3.15. Contingency space - planar representation ............................ 82

3.16. Contingency space - 3-D surface representation .................... 83

3.17. Overview of the Conditional Planning Decision Framework . 86

3.18. General Framework for Conditional Planning Decision ........ 88

3.19. Establishing the Conditional Planning Value .......................... 92

3.20. The Conditional Planning Decision Making Phase ................. 94

3.21. The Conditional Planning Decision Framework ...................... 97

3.22. Conditional planning examples .................................................. 98

4.1. Vocabulary for Describing Contingencies in the Driving

Domain ......................................................................................... 106

6.1. Situations for the ICU domain ........................................................ 148

7.1. Extended system architecture ........................................................ 157

A1.1 System Architecture and Information Flow ............................. 160

A2.1. Vocabulary for Describing Reactions in the Driving

Domain ......................................................................................... 163

A2.2. Vocabulary for Describing Situations in the Driving

Domain ......................................................................................... 165



Chapter 1

Introduction

How should an intelligent agent prepare to satisfy a goal, while being able to respond to the great variety of contingencies that might impede its achievement of goals? Short answer: through planning. For a more comprehensive answer, you may want to read this thesis. It may provide you with a partial answer to this question, but it may also raise many other questions.

Many AI research resources have already been devoted to finding solutions to the problem of planning, usually defined as choosing the next step or steps for the execution of a system, based on knowledge of the present situation, the system's goals, and the operators available. The essence of planning in AI is the ability to reason about actions and their effects, and equally important, this reasoning process can take place before the actual execution starts. Therefore, it must deal with all the uncertainties due to the fact that the actual situation at execution time can only be assumed at planning time, when many characteristics of the environment either cannot be taken into account, or simply cannot be known. Many activities in Computer Science can be regarded as instances of planning. One example is programming, which requires making decisions (at planning - i.e. programming - time) about actions to be performed later, at program execution time, based on expectations about the environment in which they will be executed. A computer program is a formal specification of how the resources of the computer will be applied to solve a given problem. Although conventional plans are not synonymous with programs, as also argued in [Drummond, 1989], we briefly use the analogy here for explanatory purposes. The more complex and unpredictable the execution environment is, the more contingencies can occur during a program execution. The programmer must therefore prepare the computer to properly respond to as many of these contingencies as possible, while still keeping the program within the computer resources, that is, it must still be small enough to fit in memory and must still be fast enough to give an answer in a required amount of time. The same situation occurs in all other domains in which planning is required.

A special kind of planning is reactive planning, i.e. building a set of specific perception-action rules stored in a computationally efficient form [Brooks, 1986; Agre & Chapman, 1987]. From now on, we will call this type of planning reaction, as opposed to the conventional type of planning which we will call simply planning or sometimes, to clearly distinguish it from reaction, conditional planning. To continue our parallel with computer programming, interruptions, traps, exceptions, and error treatment routines in a program can be regarded as reactions. They are executed as response to a large number of specific situations, and are not necessarily intended to ensure the successful normal continuation of the program towards completing its final goal. Sometimes, they are just intended to allow the program to interact gracefully with the environment or to help the program recover from a critical point and allow the user to intervene to facilitate the continuation of the program, or maybe to start the execution of another program, or even to write another program (to replan).

All the characteristics discussed so far for computer programming apply to most domains where planning is needed as a means of ensuring proper behavior of the system, before starting the actual execution of that system to achieve a given goal. Such domains range from "high-level" cognitive, symbolic domains like medical fields (e.g. anesthesiology, intensive care monitoring), to "low-level" manipulation domains like robot manipulator control. The common characteristics of all such domains is that their planning tasks can be (at least conceptually) translated into computer programs, and therefore conform to our previous discussion.

The same planning problem can be of very different levels of difficulty, depending on the assumptions made about the environment in which the plan is to be executed. For a well structured, "well behaved" environment which will not present "surprises" to the executing agent, the planning problem is much easier than for a more natural environment. In the latter case, many contingencies are possible during plan execution. We will call a contingency any state of the world entered by the executing agent while following a plan, that should not have occurred as a result of executing the plan up to that point. Contingencies are the effect of interactions between the agent and the environment; they occur because of: (i) predictable actions of the environment, or (ii) the unpredictability of the environment, or (iii) the unpredictability of the execution subsystems of the agent. In the real world, the number and variety of contingencies that can occur during the execution of a plan is unlimited. An ideal planner should take care of all these contingencies and build a "universal" plan [Schoppers, 1987] for the agent. As has already been shown [Ginsberg, 1989], building such a plan is not feasible for interesting application domains, due to practical limitations of the agent's resources. However, many of these contingencies can be ignored, either because they do not seriously affect the execution of the plan or because they have an extremely low likelihood of occurrence. Some of the remaining contingencies may have a very high likelihood of occurrence while also requiring elaborate subplans to treat them. Therefore, these subplans should be included as conditional branches in the original plan. Other significantly less likely contingencies may allow for a very short time of response, while having disastrous consequences if the response does not occur in time. Such contingencies probably should be treated reactively. These reactions need not lead the agent to the final goal of the initial plan; it is enough if they can stabilize the situation, avoid the consequences of the contingency, and allow the planner to replan a comprehensive solution from the current situation to the final goal. Yet other contingencies, not extremely likely and without short term dramatic consequences, can be ignored at planning time and left for a possible replanning phase at execution time: when they appear, the agent (which is not under very high time pressure) can suspend execution and take its time to replan a solution from that situation to the final goal. This may involve either a complete solution or, more frequently, a patch to bring the agent back to one of the states in its original plan from which it can continue execution (one such mechanism was implemented by the triangle tables used in STRIPS [Nilsson, 1984]).

From the above discussion we can derive the two basic control modes for an agent that must deal with such contingencies: planning and reaction. By planning we will understand here both building a course of action before starting its execution and dynamic replanning, i.e. interleaving planning with execution. Each of these two modes has its advantages in certain circumstances, and we shall summarize them here. [Hayes-Roth, 1993] presents a complete discussion of these characteristics.

Among the strengths of the planning model is the fact that plans can be built to have a set of desirable global properties regarding the goals to be attained and the resources of the agent. The side effects of the actions to be executed as part of the plan can be carefully taken into account and analyzed before execution begins. These properties are achieved by taking into account complete descriptions of the states of the world as they are predicted by the planner. Of course, these states will conform to reality only if the environment behaves according to the model that the planner has about it. The more incomplete this model is, the more uncertainty in the behavior of the environment, and the more uncertainty about the actual states that will be encountered by the agent during plan execution. The final plan has a high degree of coherence and is easily comprehensible by a human user (this last point is very important in domains where the entire credibility of the system depends on how much a user can understand from the reasoning of the system, such as medical domains). The plan generated by a conditional planner usually makes a close approximation of the optimal usage of the agent's resources. Finally, the planned actions can be executed promptly at run time (since the agent simply follows a completely specified plan, in which the next action is taken according to the plan, maybe after evaluating the results of some tests in the case of conditional plans). However, the planning model has its weaknesses with respect to the real world. The two main disadvantages are: (i) the high computational cost of planning (which makes it necessary to carefully consider which contingencies should be exhaustively treated in this way - otherwise the time to build the plan may become prohibitive); and (ii) the inflexibility of the planned behavior - the agent can only act in states of the world which are specified in the plan, and its performance will degrade very abruptly with any variations to such states.

The reactive model constructs a set of goal-specific perception-action rules and stores them in a computationally efficient form. The main advantages of the reactive model are its flexibility of response to a larger set of run-time conditions (since each response is less carefully analyzed than in the previous case, and the response does not need to embody a complete solution to the final goal but can merely be an action to stabilize the situation and allow the time for replanning) and its short time of response (determined by the efficient way of storing the reactive plan). On the other hand, reaction still cannot anticipate, distinguish and store all runtime contingencies. It will therefore still exhibit precipitous failure in unanticipated conditions. But the main disadvantage of reaction is that it is taken after a superficial evaluation of the current state, and does not benefit from an in depth analysis of this state and the related action consequences. Therefore, while a reaction may be locally appropriate, its global effectiveness is uncertain.

The planning and reactive control modes are near the end-points of a theoretical continuum of control modes. Together with two other control modes (reflex and dead-reckoning), they form a two-dimensional space described in [Hayes-Roth, 1993]. Also analyzed there is the correspondence between the space of control modes and a two-dimensional space of control situations, as well as the effect of combining the control modes in different degrees on the quality of run-time behaviors in the corresponding space of control situations.

We believe that planning and reacting complement each other, and therefore we envision agents that: (a) plan courses of action designed to achieve goals under certain anticipated contingencies - conditional branches are built in the plan for the very likely contingencies that also require significant planning to reach the goal; (b) augment these plans with context-dependent reactions for noticing and responding to less likely, but important exogenous events; (c) control their behavior by following their plans, while simultaneously monitoring for and, when appropriate, executing reactions associated with particular phases of their plans; and (d) revise their plans when local reactions do not adequately address unanticipated events.

However, this complementarity of the planning and reaction control modes in intelligent agents is overlooked by many researchers today. Most planning research to date has been concentrated either towards just one of the two control modes, or when it attempts to combine them, the main purpose is to increase the reactive capabilities of the agent and to unload the conventional planner's responsibilities. In this latter case, the general assumption is that reaction comes for free, that is, either the agent's resources are unlimited or the reaction process does not use any significant amount of the agent's resources. Unfortunately, this is not the case in reality: any real agent has limited resources, and the reaction process may use significant amounts of the agent's resources. This fact has a couple of consequences: (i) a decrease in the reactive responsiveness of the agent (or equivalently an increase in its response time to a given contingency), which may make some reactions useless if they come too late, and (ii) a limitation in the number of reactions for which the agent can prepare in a given situation. This means that the agent must be more selective in the types of reaction it prepares for each situation, preparing the most important reactions and ignoring the others. In the following chapters we define and characterize the value of reactions and identify those characteristics of the agent and its working environment that influence the response capabilities of the agent to different situations that it may encounter in its working environment. Based on this analysis, we formulate a framework to decide, at planning time, which control mode to choose for contingencies that may appear during plan execution, that is, a framework to decide, at planning time, whether a certain situation requires special preparation for a possible reactive response, or whether it can be left for dynamic replanning at execution time. The problem is particularly important for planning the activity of an intelligent agent which must work in a dynamic, complex, unpredictable real-time environment.

The approach begins with a plan designed to achieve a goal and enhances it to cope reactively with critical contingencies, while maintaining the size of the plan and the planning and response times within reasonable limits. The framework can also be modified for the problem of deciding, for a given contingency, whether to prepare a special branch in the (conditional) plan or to leave the contingency for opportunistic treatment at execution time.

As an example, consider driving a car between two given locations. Before starting, the driving agent plans its route in some detail, including turns at intersections and expectations of achieving milestones along the way, in order to minimize travel time. It also prepares a conditional branch in its plan as an alternative route in case the original route is blocked at a certain intersection where blockage is highly probable. This conditional branch requires extensive planning resources but produces a complete solution that leads all the way to the final goal. Along the way, the agent in fact encounters unexpected heavy traffic and revises the remainder of its plan to take an alternate route. As it follows the revised plan, the agent passes a school, where it watches carefully for children who might suddenly run into the street. As it leaves the neighborhood of the school and enters an industrial area, the agent forgets about children and watches for other contingencies (e.g., railway crossings, trucks coming out of driveways). Note that the agent, while executing the plan, is prepared to react to certain contingencies at different stages of the plan, while using dynamic replanning to solve other contingencies.

Given certain conditions (like the time of day, the weather, the type of roads to be used) the agent prepares in advance for possible contingencies that may appear on certain portions of the trip. However, it does not include expectations for and responses to these contingencies as steps of the plan, since they are not essential for the plan to be executed successfully. On the other hand, if they happen and are not responded to properly, they may preclude the successful completion of the plan. Examples of such contingencies are: sliding on a slippery road in cold weather, an unsignalled object in the street during night time, a child running in front of the car from a nearby school, or a traffic jam at rush hours. Note that these contingencies were qualified by the characteristics of the situation in which they are likely to appear. For some such contingencies, a reactive response must already exist since the situation does not allow enough time for the agent to replan a solution. There exists an infinite set of such contingencies, so the agent cannot prepare to always react to all of them. Moreover, due to limited computational and non-computational resources, if the agent prepares for too large a set of contingencies in a situation, selecting the correct response for the one that actually occurs may become a too long process, thus rendering the response ineffective. However, the responses to such contingencies do not need to include an entire solution to the main plan's ultimate goal; if the agent responds to them fast enough to avoid unwanted consequences, then it may take the time to replan the entire solution from there on. Since these contingencies are too many and not very likely, they do not warrant a complete conditional branch in the initial plan to lead to the final goal.

Therefore, we need a decision framework to guide the selection of contingencies for which a reactive response should be prepared at planning time. This need arises in many domains besides car driving (for example, in intensive care monitoring, anesthesiology [DeAnda & Gaba, 1991; Fish & al, 1991; Gaba & al, 1991; Gaba 1991], nuclear power plant operation [Woods & al., 1987]). Formulating this framework is an important step toward building the control engine of real-time intelligent agents with limited resources for such domains. The formulation and evaluation (theoretical and experimental) of such a framework is the topic of this research.

In the following chapter, we outline the problem in more precise terms. We define the notion of contingency and classify contingencies into types according to their importance and the way they should be treated by the agent (with conditional plans, with reactions, or simply ignored at planning time and left for dynamic replanning if necessary). We also characterize the domains where the framework developed here will be most applicable. Finally a review of related work points out similarities with other paradigms.

Chapter 3 presents the basic approach. After giving an intuitive solution for a simple problem in the driving domain and analyzing this solution, we present the details of the framework for the reaction preparation decision. We show how it can be used to establish the value of reacting to a contingency in a given situation and to make the decision of whether to plan to react to that contingency. The chapter closes with a discussion of how this framework may be modified and applied to decide whether a certain contingency, in a given situation, requires preparation of a complete branch in the initial conditional plan.

Chapter 4 discusses a proposal for a knowledge representation formalism for contingencies, reactions and situations, to facilitate the structuring of the planner's knowledge and its manipulation.

Chapter 5 presents a theoretical analysis of the framework presented in chapter 3 for deciding whether to plan to react to a given contingency in a given situation. A few formal properties are stated and justified, to support claims of generality and optimality (in terms of using the agent's resources) for the proposed formalism.

Experimental demonstrations are then presented and briefly analyzed in chapter 6. Three domains were used for this purpose: an everyday domain where everyone is an "expert" (car driving) and two highly specialized medical domains of expertise (anesthesiology and intensive care monitoring). Results include simulations of several models of human reactive behavior discussed in the literature. A demonstration in a complex, real-world application domain shows: (1) that the knowledge and data needed for the decision making process exists and can be acquired from experts in that domain; and (2) that the behavior of the agent improves (according to response time, reliability and resource use criteria) as a result of incorporating our decision framework in the agent's planning mechanisms.

After summarizing our work, we make in chapter 7 a few suggestions of natural continuations of this research, including applications of case based reasoning techniques for managing a library of reactive plans and a library of contingencies and reactions, and several applications of learning mechanisms to different parts of our framework.

Appendix 1 briefly presents the architecture of the reaction decision module and the interface for integrating the module in an intelligent agent.

Appendix 2 completes the vocabulary example started in chapter 4 for the driving domain. It presents a large enough grammar to represent most of the situations, contingencies and reactions used as examples from this domain throughout the thesis.

In appendix 3 we present the results of a number of experiments we have conducted in the anesthesiology domain, in order to provide further evidence regarding the generality and applicability of our framework in real-world domains.

Finally, appendix 4 complements the presentation of intensive care monitoring domain experiments in chapter 6, by presenting a few complete sets of contingencies as they were ranked by our framework.




Download 1.35 Mb.

Share with your friends:
  1   2   3   4   5   6   7   8   9   ...   16




The database is protected by copyright ©essaydocs.org 2022
send message

    Main page