FORR
Encyclopedia
FORR is a cognitive architecture
for learning
and problem solving
inspired by Herbert Simon's ideas of bounded rationality
and satisficing
. It was first developed in the early 1990s at the City University of New York
. It has been used in game playing
, robot pathfinding, recreational park design, spoken dialog systems
, and solving NP-hard
constraint satisfaction problems
, and is general enough for many problem solving applications.
are not optimal, but make decisions based on only a subset of all possible good reasons and informative data. These agents can still be considered rational. This idea of bounded rationality
was introduced by Herbert Simon
, who along with Allen Newell
developed the early foundations of the study of cognitive architectures and also inspired early architectures such as Soar
and ACT-R
.
The tiered Advisor system is general enough that any potential good reason, such as probabilistic, deductive
, or perceptual
can be implemented, so long as it gives advice on its preference of one action over another.
Because of its reliance on a set of independent agents (the Advisors), FORR can be considered a connectionist
architecture.
component of the architecture. Upon each new decision, Advisors are queried in order to decide which action to perform. Advisors never communicate with each other or learn on their own: they simply ask for information about the state of the problem stored in the form of descriptives, and make a suggestion based on that information. The Advisors are divided into three tiers, which are queried in the following order:
component of the architecture, the descriptives represent the state of the problem and are available to any Advisor.
is a problem class, and one particular game of tic-tac-toe is a problem instance. If navigating a maze is the problem domain, then a particular maze is the class and one attempt at its navigation is an instance. Once the problem problem domain is identified, the implementation of a FORR architecture for that domain has two basic stages: finding possible right reasons (the Advisors) and learning their weights for a particular class.
vary between implementations.
, park design, and spoken dialog systems
.
Cognitive architecture
A cognitive architecture is a blueprint for intelligent agents. It proposes computational processes that act like certain cognitive systems, most often, like a person, or acts intelligent under some definition. Cognitive architectures form a subset of general agent architectures...
for learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
and problem solving
Problem solving
Problem solving is a mental process and is part of the larger problem process that includes problem finding and problem shaping. Consideredthe most complex of all intellectual functions, problem solving has been defined as higher-order cognitive process that requires the modulation and control of...
inspired by Herbert Simon's ideas of bounded rationality
Bounded rationality
Bounded rationality is the idea that in decision making, rationality of individuals is limited by the information they have, the cognitive limitations of their minds, and the finite amount of time they have to make a decision...
and satisficing
Satisficing
Satisficing, a portmanteau "combining satisfy with suffice", is a decision-making strategy that attempts to meet criteria for adequacy, rather than to identify an optimal solution...
. It was first developed in the early 1990s at the City University of New York
City University of New York
The City University of New York is the public university system of New York City, with its administrative offices in Yorkville in Manhattan. It is the largest urban university in the United States, consisting of 23 institutions: 11 senior colleges, six community colleges, the William E...
. It has been used in game playing
General Game Playing
General Game Playing is the design of artificial intelligence programs to be able to play more than one game successfully. For many games like chess, computers are programmed to play these games using a specially designed algorithm, which cannot be transferred to another context. For example, a...
, robot pathfinding, recreational park design, spoken dialog systems
Spoken dialog system
A Spoken dialog system is a dialog system delivered through voice. It has two essential components that do not exist in a text dialog system: a speech recognizer and a text-to-speech module.-Components:* Speech recognizer* Text-to-speech...
, and solving NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
constraint satisfaction problems
Constraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.The techniques used in...
, and is general enough for many problem solving applications.
Bounded rationality
FORR does not have perfect knowledge of how to solve a problem, but instead learns from experience. Intelligent agentsIntelligent agent
In artificial intelligence, an intelligent agent is an autonomous entity which observes through sensors and acts upon an environment using actuators and directs its activity towards achieving goals . Intelligent agents may also learn or use knowledge to achieve their goals...
are not optimal, but make decisions based on only a subset of all possible good reasons and informative data. These agents can still be considered rational. This idea of bounded rationality
Bounded rationality
Bounded rationality is the idea that in decision making, rationality of individuals is limited by the information they have, the cognitive limitations of their minds, and the finite amount of time they have to make a decision...
was introduced by Herbert Simon
Herbert Simon
Herbert Alexander Simon was an American political scientist, economist, sociologist, and psychologist, and professor—most notably at Carnegie Mellon University—whose research ranged across the fields of cognitive psychology, cognitive science, computer science, public administration, economics,...
, who along with Allen Newell
Allen Newell
Allen Newell was a researcher in computer science and cognitive psychology at the RAND corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department of Psychology...
developed the early foundations of the study of cognitive architectures and also inspired early architectures such as Soar
Soar (cognitive architecture)
Soar is a symbolic cognitive architecture, created by John Laird, Allen Newell, and Paul Rosenbloom at Carnegie Mellon University, now maintained by John Laird's research group at the University of Michigan. It is both a view of what cognition is and an implementation of that view through a...
and ACT-R
ACT-R
ACT-R is a cognitive architecture mainly developed by John Robert Anderson at Carnegie Mellon University. Like any cognitive architecture, ACT-R aims to define the basic and irreducible cognitive and perceptual operations that enable the human mind....
.
Multiple good reasons
FORR depends upon the idea that there are multiple reasons or rationales for performing actions while solving a problem. These reasons can be always right (it's always right to make a move in chess that will put the opponent in checkmate) or just sometimes right. The always-right reasons are the minority. The sometimes-right reasons can complete with each other: for example, in game playing, one good reason might be to capture pieces, while another might be to control some area of the board. In FORR, these competing reasons are called Advisors.The tiered Advisor system is general enough that any potential good reason, such as probabilistic, deductive
Formal logic
Classical or traditional system of determining the validity or invalidity of a conclusion deduced from two or more statements...
, or perceptual
Perception
Perception is the process of attaining awareness or understanding of the environment by organizing and interpreting sensory information. All perception involves signals in the nervous system, which in turn result from physical stimulation of the sense organs...
can be implemented, so long as it gives advice on its preference of one action over another.
Because of its reliance on a set of independent agents (the Advisors), FORR can be considered a connectionist
Connectionism
Connectionism is a set of approaches in the fields of artificial intelligence, cognitive psychology, cognitive science, neuroscience and philosophy of mind, that models mental or behavioral phenomena as the emergent processes of interconnected networks of simple units...
architecture.
The Architecture
A FORR architecture has three components: a set of descriptives that describe the state of the problem, a tiered set of Advisors that are consulted in order to decide what action to perform, and a behavioral script that queries the Advisors and performs the action that they suggest.Advisors
The Advisors are the set of rationales or heuristics for making a decision. They can be considered the procedural memoryProcedural memory
Procedural memory is memory for how to do things. Procedural memory guides the processes we perform and most frequently resides below the level of conscious awareness. When needed, procedural memories are automatically retrieved and utilized for the execution of the integrated procedures involved...
component of the architecture. Upon each new decision, Advisors are queried in order to decide which action to perform. Advisors never communicate with each other or learn on their own: they simply ask for information about the state of the problem stored in the form of descriptives, and make a suggestion based on that information. The Advisors are divided into three tiers, which are queried in the following order:
- Tier 1: these Advisors are always right. If these suggest an action, that action is carried out immediately and the query ends. If they forbid an action, that action is removed from consideration. Otherwise, move to the next tier.
- Tier 2: if one of these Advisors is triggered, it proposes a sub-problem, or an ordered set of actions, achieving a sub-goal in solving the overall problem (such as moving around one obstacle in a maze). If no tier 2 advisor is triggered, move to last tier.
- Tier 3: these are all other rationales. They are not always right, but compete with each other. They vote on an action, and the highest-voted suggestion is performed. Different problem classes in the same domain will have different weights for the same Advisors, and the weights are developed from experience through learningMachine learningMachine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
algorithms.
Descriptives
The declarative memoryDeclarative memory
Declarative memory is one of two types of long term human memory. It refers to memories which can be consciously recalled such as facts and knowledge. Its counterpart is known as non-declarative or Procedural memory, which refers to unconscious memories such as skills...
component of the architecture, the descriptives represent the state of the problem and are available to any Advisor.
Behavioral script
The behavioral script queries each tier of Advisors sequentially. If a tier 1 Advisor suggests an action, the script performs the action. Otherwise, if a tier 2 Advisor is triggered, it means that a sub-problem has been encountered. A tier 1 Advisor guarantees that only one tier 2 Advisor is active at any time. If no tier 1 Advisor comments and no tier 2 Advisor is triggered, the behavioral script asks for suggestions or comments from all tier 3 Advisors and lets them vote. The script performs the action with the highest vote among all tier 3 advisors.Implementing a FORR architecture
A problem domain is a set of similar problems, called the problem classes. If the problem domain is playing simple board games, then tic-tac-toeTic-tac-toe
Tic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first...
is a problem class, and one particular game of tic-tac-toe is a problem instance. If navigating a maze is the problem domain, then a particular maze is the class and one attempt at its navigation is an instance. Once the problem problem domain is identified, the implementation of a FORR architecture for that domain has two basic stages: finding possible right reasons (the Advisors) and learning their weights for a particular class.
How to build a FORR architecture
- Decide on a problem domain.
- Use domain knowledge, surveys of the literature, intuition and good sense to enumerate a list of possible rationales for making a decision, which can be good or bad for different classes within the domain. These rationales are the Advisors.
- Divide the Advisors into tiers:
- The Advisors that are always right are in Tier 1. For example, it's always right to make a winning move in a board game.
- The Advisors which identify a sub-problem go into Tier 2. For example, going around a wall in a maze.
- Every other Advisor is Tier 3.
- Code the Advisors. Each Advisor returns a set of suggested actions along with weights for each suggested action. The weights are initially set to a uniform value, such as 0.05.
- Identify all information about the state of the problem needed by all Advisors. These are the descriptives. Code these.
- Code the behavioral script which queries the Advisors and performs the action they suggest.
- Learn the weights for the Advisors on a set of particular problem instances in the Learning Phase using a Reinforcement learningReinforcement learningInspired by behaviorist psychology, reinforcement learning is an area of machine learning in computer science, concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward...
algorithm. - Test the architecture on a set of previously unencountered problem instances.
Learning Advisor weights
The Advisors are the same for all problem classes in a domain, but the weights can be different for each class within the domain. Important heuristics for tic-tac-toe might not be important for a different board game. FORR learns the weights for its tier 3 Advisors by experience. Advisors that suggest an action resulting in failure have their weights penalized, and Advisors whose suggestions result in success have their weights increased. Learning algorithmsReinforcement learning
Inspired by behaviorist psychology, reinforcement learning is an area of machine learning in computer science, concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward...
vary between implementations.
Applications
FORR has been used for game playing, robot pathfinding, constraint satisfaction problemsConstraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.The techniques used in...
, park design, and spoken dialog systems
Spoken dialog system
A Spoken dialog system is a dialog system delivered through voice. It has two essential components that do not exist in a text dialog system: a speech recognizer and a text-to-speech module.-Components:* Speech recognizer* Text-to-speech...
.