The Binomial Bookstore

PLANNING FOR REAL TIME EVENT RESPONSE MANAGEMENT
by David W. Ash, Vlad G. Dabija

“Two leading artificial intelligence experts cover the key issues associated with real-time and
reactive planning in intelligent agent systems. This book explains the technology in-depth,
and shows how it can be employed for maximum impact. Includes a comprehensive
real-world case study.”

- - - - - -

- “Real-time intelligent agents: solutions and applications

- Choosing and integrating the best planning techniques

- Reaction decision frameworks and language frameworks

- Includes a complete case study.”

- - - - - -

“The act of planning for and responding to real-time events has been an area of intense
investigation in the past few years. Planning for Real Time Event Response Management
offers this state-of-the-art technology in depth and demonstrates how it can be employed for
maximum effect. The techniques presented here are applicable to an exceptionally broad
range of problems, from web-based shopping assistants to robots, medicine to financial
analysis. Coverage includes:

- Conventional and reactive planning: when to use each, and when to avoid planning

- A flight planning example used throughout the book to bring together the concepts

- Key reactive planning techniques such as Brooks' subsumption architecture and
Rosenschein/Kaelbling's situated automata—and their limitations

- Contingencies: building intelligent agents that can handle unanticipated events

- Applying planning paradigms to real-world domains

- Building Reaction Decision Frameworks that integrate conventional and reactive
planning

- Solving problems at execution time: anytime algorithms and real-time architectures

- Real-time planning: integrating artificial intelligence and real-time computing.”

- - - - - -
“Planning for Real Time Event Response Management introduces a framework for
describing reactive behavior that can be used in many knowledge domains, concluding with
a preview of the next steps to be taken in intelligent agent development, including integration
of real-time problem solving languages with existing Internet infrastructures.”

- - - - -- - - - -

EXCERPT FROM THE INTRODUCTION

“In the course of our daily lives, we are frequently called upon to make decisions under time
pressure. For example, if we are driving to work, we want to plan out a trip that will get us
there on time. However, it is very difficult to be absolutely certain that we will make it on time.
We may be able to plan for the possibility of heavier-than-usual traffic and allow a little extra
time. Or we may be able to consider the possibility of a flat tire and still be able to make it to
work on time. We may allow for these possibilities by planning out alternate routes in
advance, or simply by responding to the events as they arise, or through some combination
of these approaches.

“However, it is very difficult for us to guarantee absolutely that we will get to work under all
possible scenarios. Some scenarios may be too unlikely to be worth planning for-for
example, an earthquake shutting down all major streets on the way. Some scenarios may be
too costly to prepare for-we may, for example, estimate that the cost of a bulletproof car is
not
justified given the relatively low risk of being shot in a particular neighborhood. We have to
make trade-offs. And not only do we have to make trade-offs, we have to make the trade-offs
quickly-we don't have all day to plan out the optimal way for getting to work.

“Once we get to work, we will likely be faced with a new set of problems that require us to
make trade-offs based on real-time constraints. We are expected to reach a deadline on a
particular project. However, meeting that deadline requires that we know when different
resources will be available to us. What if a key project member resigns? Do we have a
contingency plan for dealing with this? Should we spend some time planning for such
eventualities? What if the time we spend planning begins to slow down the project?

“Then, we fly to a business meeting in another city, and the pilot in charge of the flight has to
deal with real-time considerations. Does he have enough fuel on board to get to the
destination airport? Does he have enough fuel on board to get to a different airport if the
destination airport is unexpectedly closed? Does he have enough fuel on board to get to
every possible airport that a terrorist might want to hijack the plane to? Again, there are many
real-time considerations. Faced with all this stress, perhaps we end up in the intensive care
unit where the physician in charge will have yet another set of real-time constraints that he or
she has to take into account. And it goes on and on.

“These are the types of considerations that we as modern human beings face in our daily
lives. And, as more and more aspects of our lives become automated, these are
considerations that software is also going to need to become aware of and capable of
handling in an effective manner. Some of these problems could possibly be "solved"
statistically if we had enough data and time. If such resources were available, it would be
worth doing so. However, human beings routinely have to make real-time decisions without
anything even close to complete statistical information. Software will need to be capable of
doing the same.

“What this book shows are a number of techniques by which we can make these real-time
choices in an intelligent manner. Certainly, it is intended that these approaches can be
applied by the designer of a software system in solving real-time problems automatically.
There is also another, pedagogical application of the ideas presented in this book. As
humans begin to understand how to solve real-time problems automatically, they can look
back at their own processes and see whether they are being solved in the most efficient way
possible. Such an analysis will likely lead either to greater efficiency in human processes, or
else to a better understanding of how humans solve problems effectively in real time, which
will lead to better software engineering.

“A concept that appears throughout this book is that of an intelligent agent. An agent is
anything that can, through its interaction with the environment, change the state of that
environment. Examples of agents are: humans, other live beings, computer programs-any
objects that in any way interact with their environment. An intelligent agent is an agent,
human
or otherwise, that exhibits a behavior that would be considered evidence of intelligence.

“Note that such behavior need not be optimal for a specific domain or situation in order to be
considered intelligent. A more restrictive definition of intelligent agent may require that the
agent behaves in the same way as a human being with knowledge in that specific domain.
Unless otherwise specified, we will use this more restrictive definition when discussing an
agent's behavior in a restricted or specialized domain.

“In all these cases, the principal or agent (human or software) must make decisions to
optimize the outcome and the use of resources. It will therefore exhibit what is commonly
referred to as intelligent behavior.

“An intelligent agent needs to be able to respond effectively in real time in order to operate in
most real-world domains. We should, right at the outset, be clear on what we mean by
"respond effectively in real time," since the term real time is used in different contexts to
mean different things. By real time, we mean that there is some type of deadline, or at least
degradation in the utility of the agent's response, so that fast response is not only desirable
but required. Effective response by an intelligent agent means that the agent is capable of
making trade-offs of some type in order to meet the deadline.

“An example may help to illustrate what we do-and do not-consider to be "real-time
response." There are many software programs running on the World Wide Web; these
programs are often characterized as real-time because they are able to respond to the click
of a button. However, we shouldn't consider these programs to be real-time because their
responses to real-time constraints are not intelligent. Most programs on the Web allow the
user to click a button, but then the user is left at the mercy of the system as to how long the
response takes. Often it is very fast, but sometimes the user is left hanging for many
seconds
or minutes. Rarely is anything intelligent done in response to such a delay. An intelligent
trade-off might be, for example, to offer the user the chance to receive the response by email
later if it isn't available in under thirty seconds. This would free the user to do other tasks,
while still providing a response of some utility.

“It is common as we move into the new millennium to think of intelligent agents as being
necessarily deployed on the World Wide Web. While the previous example shows that the
Web is certainly one place where an intelligent agent can be deployed, we think of agents in
a broader context. For example, consider the problem of a parachutist who perceives a
delay
in a parachute opening. The parachutist has a couple of tests that he or she can perform to
determine the nature of the problem. She or he can look up at the partially opened parachute
to attempt to determine the nature of the problem, or he or she can look at the altimeter for a
few seconds to determine the rate of descent. However, the parachutist has only a limited
amount of time in which to respond before hitting "ground zero," so the parachutist may need
to act with less than complete information. From our point of view, the parachutist is
functioning as an intelligent agent.

“The ideas presented in this book are intended to be applicable to any type of intelligent
agent. An agent can be a software program (an "intelligent software agent"), a robot, a
human being, or virtually anything else capable of responding to its environment. The
purpose
of this book is to show how to handle trade-offs of the types required in the Web and
parachuting examples. To what extent is planning required? How should the agent deal with
unexpected contingencies that may interfere with executing a plan? Should the agent be
prepared to deal with all possible contingencies, with those most likely, or with those that
have the most negative consequences if action is not taken?

“This book presents state of the art real-time event response management. We will describe
a variety of approaches that are available to solve problems such as the ones we have just
outlined. We describe in which types of situations the different approaches are likely to be
useful, and we leave it to the reader to decide which particular approaches to apply to his or
her individual problem.

“This book will be of interest to anyone designing a system capable of functioning in a
real-time, dynamic domain. Software managers developing software in real-time domains-in
medicine, aviation, finance, transportation, nuclear power plant safety, engineering, Web
applications, and many others-will be able to use these approaches to develop more
intelligent systems. Higher levels of management, such as department managers and CIOs,
will also find this book useful, as the real-time nature of many problems often impacts design
decisions at the highest levels. Project managers who work extensively with software
systems will also benefit from this book, as the real-time nature of many business problems
and the incomplete nature of the information available at decision time often impacts on both
the software and the human intelligent agents in a business environment.

“Software managers will probably benefit most from the technical sections of the book, in
particular Chapters 2 through 6. They may also be interested in chapter 1, although they may
find this too high a level. Higher levels of management will probably benefit most from
Chapter 1, as well as Chapter 8, which give a high-level overview without too much technical
detail. Project managers who work with software systems will probably have a similar
interest
as software managers, although they may be able to skip sections 2.1 through 2.4, and 6.2
through 6.3.”

- - - - -

TABLE OF CONTENTS

ACKNOWLEDGMENTS

ABOUT THE AUTHORS

INTRODUCTION

1. EVOLUTION OF PLANNING.
A Brief History of Planning.
Types of Domains Used In AI.
Conventional Planners.
Pure (Hard-Wired) Reaction.
Classical Real-time Planners.
Book Synopsis.

2. SUBSUMING PLANNING TO REACTION.
Minton's Utility Function.
Insect Intelligence and Robotics: The Work of Rodney Brooks.
Procedural Reasoning Systems.
Situated Automata and Situated Agents.
Disadvantages and Next Step.

3. INTEGRATION OF PLANNING AND REACTION.
The Planning to Reaction Spectrum.
The Contingency Space.
The Need for Deciding Between Planning and Reaction.

4. DECIDING AT PLANNING TIME.
Alternative Approaches. Empirical Approach.
Analytical Approach.
The Need for Good Real-time Components.

5. EXECUTION TIME: REACTING, (RE)PLANNING AND DECIDING.
Anytime Algorithms.
Action-based Decision Trees.

6. REAL-TIME PLANNING.
Guaranteeing Temporal Adequacy.
Building Guaranteed And Unguaranteed Plans.
7. APPLICATIONS.
A Language Framework for Describing Reactive Behaviors.
Formalizing Reaction Decisions in Critical Domains for Pedagogical Purposes.

8. CONCLUSION.
Integration of the Ideas.
Language Development.
Integration with Existing Technologies.
Development of Hardware.

INDEX

- - - - -

ABOUT THE AUTHORS

“Dr. David Ash graduated from Stanford University in 1993 with his Ph.D. in artificial
intelligence. After graduating, Dr. Ash worked until 1996 as a software developer,
quantitative analyst, and trader at D.E. Shaw & Co., a Manhattan financial services firm.
Since 1996, Dr. Ash has been employed as an artificial intelligence consultant with MindBox,
Inc., providing consulting services to MindBox clients at various locations on the East Coast.

“Dr. Vlad Dabija holds an engineering degree in computers from the Polytechnic Institute in
Bucuresti, Romania, a Ph.D. degree in artificial intelligence from Stanford University, and an
MBA with Distinction from the Wharton School of the University of Pennsylvania. He worked
in several computer technology, production, research, and academic institutions in the US,
Japan, and Western and Eastern Europe before joining the venture capital firm CMEA
Ventures.”

- - - - -
2000, 401 pages. Order #DR576.
- - - - -

The Binomial Bookstore

Other Valuable Resources & Tools

Rothstein Associates Inc.