RALPH-MEA is a Real-Time, Decision-Theoretic Agent Architecture, designed for a mobile robot control system, providing navigation in a simulated environment, containing a number of fixed and moving obstacles, and developed by Gary Hayato Ogasawara, as his PhD thesis under Stuart J. Russell, in the Computer Science Division at the University of California at Berkeley, CA, USA.
RALPH-MEA | RALPH architecture |
Stuart J. Russell
Computer Science Division
University of California at Berkeley
Berkeley, CA, USA
The Center for Intelligent Systems at Berkeley
RALPH (S.J. Russell and E.H. Wefald, 1989-1991)
Когнитивная архитектура RALPH-MEA разрабатывалась как диссертационная работа Гэри Огасавара (G.H. Ogasawara) под руководством Стюарта Рассела (Stuart J. Russell) в Университете штата Калифорния в Беркли (University of California at Berkeley), Калифорния, США.
Now Gary Ogasawara works for Cloudian, Inc. (formerly Gemini Mobile Technologies), Foster City, California, based software company specializing in cloud storage software.
RAPLH-MEA: Architecture Description
The dissertation of G. H. Ogasawara (Advisor: Stuart J. Russell):
This dissertation describes the RALPH-MEA agent architecture which uses decision theory combined with real-time control for decision-making in complex domains. In order to achieve the conflicting goals of an accurate representation and a fast decision cycle, several novel techniques are introduced.
Multiple execution architectures are four implementations of the agent function, a function that receives percepts from the environment as input and outputs an action choice.
The four execution architectures (EAs) are defined by the different knowledge types that each uses. Depending on the domain and agent capabilities, each EA has different advantages.
For example, a reactive, "if (condition) then (action)", production rule system will generally allow fast reactions, while a deliberative, decision-theoretic system will be slow but accurate and easily programmed with new knowledge and goals.
A metalevel algorithm to combine the results of multiple EAs is given, and a decision-theoretic representation of the EAs as "extended influence diagrams" is defined.
Knowledge compilation is used to convert knowledge of one type to another. For example, the knowledge used by a decision-theoretic system (e.g., probabilities and utilities of outcome states) can be converted into knowledge used by a condition-action rule systems.
A viable strategy is to acquire knowledge in one form and then to use knowledge compilation to convert the knowledge into the most efficiently executable form. A view of decision-theoretic planning is also presented. Utilizing decision theory for planning facilitates the handling of uncertainty and multiple objectives.
However, because of the high complexity of such planning, control of planning becomes a critical issue.
Metalevel control of planning computes the value of information of planning to compare to the utility of executing the current default plan.
Ogasawara [Oga91] has developed a mobile robot control system for navigating and map building in a simulated environment containing a number of fixed and moving obstacles. The architecture is composed of a set of task-oriented, subsumption-like behavioural modules, with one for each of the three tasks performed by the agent: Avoid Obstacles, Get to Goal, and Build Map.
The architecture also comprises a centralised world model structure and an arbitration procedure for mediating and selecting among the agent’s competing behaviours. Each behavioural module has access to a number of problem solving strategies, each differing in terms of its computational cost or solution accuracy. Behavioural modules store local (per-module) decision-theoretic formulations of the utilities of specific outcome states (for example, hitting a wall) and the probabilities of each problem solving strategy yielding a particular action sequence output. Once computed, behavioural modules send their utilities and probabilities to the arbitration module which, upon application of a multiattribute utility estimation function, will ultimately determine the agent’s optimal problem solving strategy, information action (if any), and base-level motor action.
Ogasawara and Russell brought decisition-theoretic considerations to cognitive architecture design with their RALPH architecture. Their idea was to run several modules or Execution Architectures (EA) in parallel. They vary in speed and accuracy, and RALPH tries to use the results of the one that is best, given time constraints and other factors.
The multiple knowledge types define four different paths from perception to action, called Execution Architectures:
Each Execution Architecture runs in parallel, and the arbitrator chooses which action to take, based on environmental constraints. After generating an action, RALPH-MEA executes the action and monitors its results. If an error is detected, RALPH-MEA employs its replanning component.
RALPH's reasoning is guided by the Maximum Expected Utility (MEU) principle. This principle can be summarized as "Do the Right Thing". The equation for computing the ideal action is in the Methodology section.
Each execution architecture produces its own plan according to its own knowledge types.
In particular, the Action-Utility and the Decision-Theoretic architectures utilize an MEU function to evaluate the best actions given knowledge of current and future states.
Stuart Russell and Eric H. Wefald Do the Right Thing: Studies in Limited Rationality. Cambridge, MA: MIT Press, 1991.
Gary Ogasawara and Stuart Russell ``Planning Using Multiple Execution Architectures.'' In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, Chambery, France: Morgan Kaufmann, 1993.
Wefald, Eric The Expected Value of Search: A Decision-Theoretic Framework for Game-Playing Algorithms. MS report, Computer Science Division, University of California, Berkeley, CA, 1988.
Ogasawara, Gary A Distributed Decision-Theoretic Control System for a Mobile Robot. MS report, Computer Science Division, University of California, Berkeley, CA, 1989.
Ogasawara, Gary. PhD thesis
Other useful pointers:
Book Artificial Intelligence: A Modern Approach see also AIMA - Базовый учебник по ИИ
Rationality and Intelligence, slides from the IJCAI 95 Computers and Thought lecture.
Learning in Rational Agents, slides from NIPS 97 invited talk.
What is to be done?, slides from AAAI 08 invited talk.
Life: Play and Win in 20 Trillion Moves , slides from SARA 2011 invited talk.
Unifying Logic and Probability; A New Dawn for AI? , slides from the Colloquium Sorbonne-Universités, Jan 2013.