Andreas Wendemuth, Otto-von-Guericke-Universität Magdeburg, 18.01.2009 1 SOAR Prof. Dr. Andreas Wendemuth Lehrstuhl Kognitive Systeme / Sprachverarbeitung

Andreas Wendemuth, Otto-von-Guericke-Universität Magdeburg, 18.01.20091

SOAR

Prof. Dr. Andreas Wendemuth

Lehrstuhl Kognitive Systeme / Sprachverarbeitung

Institut für Elektronik, Signalverarbeitung und Kommunikationstechnik

Fakultät für Elektrotechnik und Informationstechnik Otto-von-Guericke Universität Magdeburg

http://www.kognitivesysteme.de


SOAR

Soar is used by AI researchers to construct integrated intelligent agents and by cognitive scientist for cognitive modeling.

It can basically be considered in three different ways:


1. A theory of cognition. As such it provides the principles behind the implemented Soar system.

2. A set of principles and constraints on (cognitive) processing. Thus, it provides a (cognitive) architectural framework, within which you can construct cognitive models. In this view it can be considered as an integrated architecture for knowledge-based problem solving, learning and interacting with external environments.

3. An AI programming language.


Soar incorporates problem spaces as a single framework for all tasks

and subtasks to be solved production rules as the single representation of

permanent knowledge objects with attributes and values as the single

representation of temporary knowledge automatic subgoaling as the single mechanism for

generating goals and chunking as the single learning mechanism.


Rules (Productions) in SOAR

rules are if --> then starts with the symbol “sp”, which stands for

“Soar production.” All conditions must match.


Execution of productions A condition tests for the existence (or absence)

of data in working memory.

Rules fire: all of the actions are performed in working mememory.

All rules are global.


Structure of productionsp {rule*name(condition)(condition)…-->(action)(action)…}


Working memory

Working memory is organized as graph structures in states.

Nodes that have links (non-terminals) are identifiers, terminals are constants.

Links are attributes which point to values. An object is everything following its initial

state, which is augmentation.


Objects: e.g. two blocks on table

(s1 ^block b1 ^block b2 ^table t1)

(b1 ^color blue ^name A ôntop b2 ^type block)

(b2 ^color yellow ^name B ôntop t1 ^type block)

(t1 ^color gray ^name Table ^type table)

[also: table.color gray ]


Rules Variables <s>, <o>, cf. Values 3, 1. Commands write, halt. Example:

sp {hello-world

(state <s> ^type state)

-->

(write |Hello World|)

(halt)}


Operators and Decisions Soar must decide (select) which (acceptable)

rules fire The locus of this decision is working memory Therefore, operators are proposed, selected

and applied This is a continuous cycle Rules whose prerequisites do not match any

more are retracted (exception: operators)


Proposing A rule proposes an operator by creating an

acceptable preference (+) for the operator. Example

sp {propose*hello-world (state <s> ^type state) --> (<s> ôperator <o> +) (<o> ^name hello-world)}

<o> is an action variable which will be stored in working memory and examined later for application


Selecting Since proposing and applying are kept

separate, selection processes are possible All acceptable proposed rules with matching

conditions are always candidates for selection If no other selection procedure is programmed,

all these rules fire in parallel

[in contrast to other programming languages]


Order of selection Random order of multiple matching rules is given by

„indifferent“ preference („= “ ) in proposal, avoiding an impasse

Example:sp {water-jug*propose*fill (state <s> ^name water-jug ^jug <j>) --> (<s> ôperator <o> + ôperator <o> =) ....


Applying (firing) Example:

sp {apply*hello-world

(state <s> ôperator <o>)

(<o> ^name hello-world)

-->

(write |Hello World|)

(halt)} This rule finds all variables <o> in working memory with matching conditions and fires all of them


Persistence in Working Memory-Truth Maintenance Operator application creates persistent results

in working memory (operator-support)[Operators are commitments of SOAR]

All other rules perform their actions, and retract from working memory if their conditions fail to match (instantiation-support, i.e. work only as long as that instantiation of the rule applies).E.g. proposal, comparison, elaboration.


Operator manipulations (I) Compare and negate operators by

- (negate), < , <=, >,>=, <> (not equal) Example:

sp {water-jug*propose*fill

(state <s> ^name water-jug ^jug <j>)

(<j> -êmpty 0)

(<j> ^contents > 0)

......


Operator manipulations (II) Math in parantheses (), with prefix notation

– Example 2 +vc: (+ 2 (* <v> <c>))

Tests in parantheses {}– Example:

sp {water-jug*propose*pour

(state <s> ^name water-jug

^jug 

^jug { <j> <> })

match <j> and not equal to .


Manual removal of working memory elements by „-“ Example:

sp {water-jug*apply*fill (state <s> ^name water-jug ^jug <j>) (<j> ^volume <volume> ^contents <contents>) --> (<j> ^contents <volume>) (<j> ^contents <contents> -)}

Replaces the old value with a new one and removes the old value from memory


Remembering retracted operators Augment the current state by last-op Example:

sp {water-jug*apply*operator*record*last-operator*pour

(state <s> ^name water-jug ôperator <o>)

(<o> ^name pour ^fill-jug <fj> êmpty-jug <ej>)

-->

(<s> ^last-operator <last-op>)

(<last-op> ^name pour ^fill-jug <fj> êmpty-jug <ej>)}


Suppress operator action by „<“ Example: (if just emptied, do not fill)

sp {water-jug*select*operator*avoid*inverse*fill

(state <s> ^name water-jug ôperator <o> ^last-operator <lo>)

(<o> ^name fill ^fill-jug )

(<lo> ^name empty êmpty-jug )

-->

(<s> ôperator <o> <)}


Removing operators E.g. if last-op does not (-) have the same name and fill-jug,

remove itsp {water-jug*apply*operator*remove*last-operator*pour

(state <s> ^name water-jug ôperator <o> ^last-operator <last-op>)

( <o> ^name pour ^fill-jug <fj> êmpty-jug <ej>)

- (<last-op> ^name pour ^fill-jug <fj> êmpty-jug <ej>)

-->

(<s> ^last-operator <last-op> -)}


Detecting Success and Halting Match condition, write and halt. Example:

sp {water-jug*detect*goal*achieved

(state <s> ^name water-jug ^jug <j>)

(<j> ^volume 3 ^contents 1)

-->

(write (crlf) |The problem has been solved.|)

(halt)}


Operator Impasses - Types Operator no-change impasse: an operator has been

selected and there is no new decision to be made. State no-change impasse: no operators are proposed

for the current state. Operator tie impasse: multiple operators proposed,

but insufficient preferences to select between them. Operator conflict impasse: multiple operators

proposed, and the preferences conflict.


Impasse resolution (I) – learning in case of operator tie

Multiple operators are applicable in higher goal context = operator tie

Return to the pre-impasse environment (lower goal context) Gather features in pre-impasse environment Augment pre-impasse rules by those features Look in memory for rules (partially) using these features In those memorized rules, find additional conditions and

preferred actions based on those features Augment the lower goal context by these goal-relevant

conditions and preferred actions


Example of augmenting Options to get to the station: walk or take bus, are

unresolved (operator tie) In pre-impasse rules, a feature „available time“ was used In memory, a situation was found where the goal was to

get to the airport. Then, a condition was „available time < 30min“, and if true, a bus must be taken to catch the train.

Augment pre-impasse environment by condition „available time“ and corresponding actions.

If unavailable, get that information. Decide again.


Impasse resolution II - chunking Look at our previous example of learning. Divide the goal process (get to station) into

subgoals: (assess available time) or (determine convenient travel mode) = chunking

Make these chunks new individual rules = deductive (bottom-up) learning

Use these rules for other goals, e.g. for (visit grandma) or (spend evening with Monica)


Impasse resolution (III) – alternative operators If no (partially) matching previous memory

examples exist: Go to pre-impasse environment and gather all

conditions and corresponding rules. Follow alternative rules allowed (but e.g. not

preferred) by these conditions


Example for alternative operators Impasse: (if get to station -> walk or take bus ?) Pre-impasse conditions & rules,in reverse order:

(if get to work -> get to station) (if 08:00am -> get to work)

Other (non-preferred) rules on same conditions:(if get to work -> take car)(if 08:00am -> continue sleeping)

Use 1st matching of these rules in reverse order


Impasse Resolution IV in SOAR Learning by abduction [„Seitliches

Wegführen“] (Johnson, 1994)

= Einbettung derselben Regel in anderen Kontext

Learning by instruction [„Unterweisung“] (Huffman, 1993)

nach Anfrage von SOAR an Lehrer, oder nach Entscheidung einer „Aufsichtsperson“


Water Jug Problem You are given two empty jugs. One holds five gallons

of water and the other holds three gallons. There is a well that has unlimited water that you can

use to completely fill the jugs. You can also empty a jug or pour water from one jug

to another. There are no marks for intermediate levels on the jugs.

The goal is to fill the three-gallon jug with one gallon of water.


Solution Space Define states (gallons in jug1, gallons in jug2) Nr. of gallons can only be 0,1,2,3 (3 gallon

jug) or 0,1,2,3,4,5 (5 gallon jug) -> 24 states 4 possibilities of action:

water 1->2, water 2->1, empty, fill. All possibilities of actions on all states gives

finite and complete diagram If state (.,1) is in this diagram: problem solved



.....

M E R C I !!

Documents

Andreas Wendemuth, Otto-von-Guericke-Universität Magdeburg, 18.01.2009 1 SOAR Prof. Dr. Andreas Wendemuth Lehrstuhl Kognitive Systeme / Sprachverarbeitung