-
Explain briefly the following STRIPS concepts:
i) STRIPS assumptions
ii) World Model
iii) Operator
iv) Macro operator
- i) STRIPS assumptions
- -only one action can occur at a time
- - actions are effectively instantaneous
- - nothing changes exept as the result of planned actions
- ii) World Model
- dynamic database of facts
- iii) Operator
- Descriptions of basic actions in term of a precondition specifying when the action can occur, an Add-list and a Delete-list specifying how the World Model should be updated as a result of performing the action
- iv) Macro operator
- Pre-compiled sequence of basic actions. The sequence is planned once and for all so that it need not be planned repeatedly on multiple occurrences of these actions.
-
Autoepistemic Logic
- saying that a bird is believed to
- be flightless is not the same as saying that the bird is flightless. Suppose, for example, that we know that either bird a or bird b is flightless, but we do not know which. In this case, we know that one of them is flightless, but neither of them is believed to be flightless. Because we imagine reasoning using sentences like these, we will be reasoning about birds, of
- course, but also about what we believe about birds. The fact that this is a logic about our own beliefs is why it is called autoepistemic logic.
-
Default Reasoning
'Given that a P is generally a Q, and given that P(a) is true, it is reasonable to conclude that Q(a) is true, unless there is a good reason not to.'
-
CWA Closed World Assumption
- Unless an atomic sentence is known to be true, it can be
- assumed to be false
-
Generalized Closed World Assumption (GCWA)
preserves consistency. weaker version of CWA that agrees with the CWA in the absence of disjunctions but that remains consistent in the presence of disjunctions
-
Example Circumscription
KB: ∀x [Bird(x) ∧ notAb(x) ⊃ Flies(x)]
Facts
Bird(chilly), Bird(tweety), (tweety /= chilly), notFlies(chilly)
We would like to conclude by default that Tweety flies, whereas Chilly (the black and white Antarctic bird), of course, does not.
- KB does not include Flies(tweety) and there are interpretations where Flies(tweety) are false. but we will only consider interpretations where Ab predicate is as small as possible. Minimize abnormality.
- Default assumption is that the extension of Ab is only as large as it has to be given what we know, so should only contain/include Ab(chilly). Excludes tweety because nothing we know dictates Ab must include her. This is called circumscribing the predicate Ab.
-
Example Minimal Entailment
KB: ∀x [Bird(x) ∧ notAb(x) ⊃ Flies(x)]
Facts
Bird(chilly), Bird(tweety), (tweety /= chilly), notFlies(chilly)
We require each interpretation that satisfies KB to satisfy α except that it may be excused when there is another more normal interpretation that also satisfies the KB. Roughly speaking, we do not require α to be true in all interpretations satisfying the KB, but only in the minimal or most normal ones satisfying the KB.
-
Differences between CWA and GCWA
The difference is that GCWA will not negate controversial facts by default, i.e. facts that participate in disjunctive knowledge. The reason is that disjunctions may introduce inconsistency in the extension KB+ of KB. The closed world assumption will mimic the occasional tendency in humans to regard facts that is not explicitly mentioned to be untrue.
-
Frame axioms
describe limitations on the effects of actions
dropping object x does not change its color c
-
Taxonomies/Hasse’s Diagram
Example with vehicle
-
Subsumption ⊑
d’ subsumes d, d ⊑ d', iff the interpretation of d is a subset of that of d’. That is, every member of the concept d is also in d’.
-
Situation Calculus
- Situations
- • do(a,s0) – The situation resulting from performing action a in s0
- • do(a,do(a,s0)) – The situation after performing a twice
- Fluents
- • Predicates whose values vary based on situation
- • Situation is always an argument, such as OnTable(box, s)
- Possibility
- • Poss(a,s) states whether or not a is possible to do in state s
- Axioms
- • Precondition – Which fluents/predicates must hold for action to be performed
- Effects – Fluents changed as result of action
- Frame axioms
-
TowersOfHanoi
First we arrange the pegs to a circle, so that clockwise we have A, B, C, and then A again. Following this, assuming we never move the same disk twice in a row, there will always only be one disk that can be legally moved, and we transfer it to the first peg it can occupy, moving in a clockwise direction, if n is even, and counterclockwise, if n is odd.
WM elemets
(on peg:A disk:i), for each disk i, and an element (solve). When your rules stop firing, your working memory should contain (done) and (on peg:C disk:i), for each disk i.
Initial WM
Productions Rules
- % Disk 1 is smallest, disk 2 is bigger and disk 3 is biggest
- (on peg:A disk:1)
- (on peg:A disk:2)
- (on peg:A disk:3)
- (solve)
- (zero value:0)
- %we set the value of zero in the initial state to 0, only an even disk i has i%2 value 0 so therefore
- IF (zero value:[i%2])
- %then our disk i is even
- %to check if disk i is odd, ie. not 0, then we need to use - in our check
- IF -(zero value:[i%2])
- PRODUCTION RULES
- IF
- (solve)
- -(on peg:A)
- -(on peg:B)
- THEN
- REMOVE 1
- ADD (done)
-
TowersOfHanoi
First we arrange the pegs to a circle, so that clockwise we have A, B, C, and then A again. Following this, assuming we never move the same disk twice in a row, there will always only be one disk that can be legally moved, and we transfer it to the first peg it can occupy, moving in a clockwise direction, if n is even, and counterclockwise, if n is odd.
WM elemets
(on peg:A disk:i), for each disk i, and an element (solve). When your rules stop firing, your working memory should contain (done) and (on peg:C disk:i), for each disk i.
INITIALIZING FROM INITIAL STATE
PROCEDURES
- INITIALIZING
- %check if even
- IF
- (solve)
- -(done)
- -(FirstMove)
- -(SecondMove)
- -(ThirdMove)
- (on peg:A disk:i)
- -(on peg:A disk:[>i])
- (zero v:[i%2])
- THEN
- ADD (FirstMove)
- ADD (Assignment auxilliary:C destination:B)
- check if odd
- same as above, however
- IF
- -(zero v:[i%2])
- THEN
- ADD (FirstMove)
- ADD (Assignment auxilliary:B destination:C)
create a set of procedures for first move, second move, third move.
-
Conflict Resolution Strategy
(Order, Specificity, Recency, Refractoriness)
-
Frame Problem, p.288
Leads to Successor State Axioms (One per fluent, completely characterizes fluent in its successor state)
-
Explain what the frame problem is
The frame problem occurs when reasoning about actions. This naturally involves reasoning about the effects of actions, but since the full range of reasoning about actions also requires reasoning about non-effects, these must be represented somehow. However, there will be a vast number of non-effects to be registered. Too many for practical storage and too many for KB-designers to conceive. A solution to the problem must thus consist of a systematic/mechanical way of capturing all non-effects, using a limited amount of axioms, i.e. the representation must be cheap in terms of memory-space.
It is a set of ontological commitments, i.e., an answer to the question: In what terms should I think about the world?
determine consequences by thinking rather than acting, i.e., by reasoning about the world rather than taking action in it.
-
Which concepts subsume which among the following concepts?
A. [AND MuscleVehicle GravityVehicle
[EXISTS 1 :Platform] [EXISTS 1 :WheelType]
[FILLS :Wheelbase long]]
B. [AND MuscleVehicle
[FILLS :Platform stiff]
[EXISTS 1 :Wheelbase]]
C. [AND MuscleVehicle
[EXISTS 1 :Platform] [EXISTS 1 :WheelType] [EXISTS 1 :Wheelbase]]
C. subsumes A.
-
-
difference between entailment and entailment by refutation
- entailment is finding KB|=D(r), ending with [D(r)]
- refutation is adding the query [notD(r)] and ending with [ ], empty
-
WME John is older than mary
(basicFact relation: olderThan firstArg: john secondArg: mary)
-
Production rules
Specifications
example:
type person whose age att is exactly n+4, where n is specified somewhere else
there is no WME in the WM whose type is person and whose age value is between 6 and 23
- where each specification is one of the following:
- ■ an atom,
- ■ a variable,
- ■ an evaluable expression, within “[ ],”
- ■ a test, within “{ },”
- ■ the conjunction (∧ ), disjunction (∨ ), or negation (°˛ ) of a specification.
- rule conditions
- (person age: [n + 4] occupation: x )
−(person age: {< 23 ∧ > 6 })
-
Production rules example
We have three bricks, each of different size, sitting in a heap. We have three identifiable positions in which we want to place the bricks with a robotic “hand”; call these positions 1, 2, and 3. Our goal
is to place the bricks in those positions in order of their size, with the largest in position 1 and the smallest in position 3. Assume that when we begin, working memory has the following elements:
(counter value: 1 )
(brick name: A size: 10 position: heap )
(brick name: B size: 30 position: heap )
(brick name: C size: 20 position: heap )
In this case, the desired outcome is brick B in position 1, brick C in
position 2, and brick A in position 3.
How to achieve goal?
1. Place the largest currently available brick in the hand
2. place the brick currently in the
hand into the next position, going through the positions sequentially:
- 1. IF (brick position: heap name: n size: s )
- − (brick position: heap size: {> s })
- − (brick position: hand )
- THEN MODIFY 1 (position hand )
- In other words, if there is a brick in the heap, and there is no bigger
- brick in the heap, and there is nothing currently in the hand, put the
- brick in the hand.
- 2. IF (brick position: hand )
- (counter value: i )
- THEN MODIFY 1 (position i )
- MODIFY 2 (value [i + 1] )
- When there is a brick in the hand, this rule places it in the next
- position in sequence given by the counter, and increments the
- counter.
- When Rule 1 matches, n is bound to B and s to 30. The result of this rule’s firing, then, is the modification of the brick B WME to be the following:
- (brick name: B size: 30 position: hand )
- Now that there is a brick in the hand, Rule 1 cannot fire. Rule 2 is applicable, with i being bound to 1. Rule 2’s firing results in two modifications, one to the brick B WME (position now becomes 1) and one to the counter WME:
- (brick name: B size: 30 position: 1 )
- (counter value: 2 )
- This repeats until there no more bricks in the heap, no more in the hand, and bricks are positioned 1,2,3
- NEXT STEPS
- (brick name: C size: 20 position: hand )
- (brick name: C size: 20 position: 2 )
- (counter value: 3 )
- (brick name: A size: 10 position: hand )
- (brick name: A size: 10 position: 3 )
- (counter value: 4 )
- END
- Rule 1 nor Rule 2 is applicable. The system halts, with the final
- configuration of WM as follows:
- (counter value: 4 )
- (brick name: A size: 10 position: 3 )
- (brick name: B size: 30 position: 1 )
- (brick name: C size: 20 position: 2 )
-
Production rules
How many days in a year
WM: (wantDays year: n )
what will the WME have?
WME: (hasDays days:m ) will express the result when the computation is finished.
- WME of type year to break the year down into its value mod 4, mod 100, and mod 400.
- (year mod4: [n %4] mod100: [n %100] mod400: [n %400] )
-
Production rules
How many days in a year
WM: (wantDays year: n )
WME:
(hasDays days:m )
(year mod4: [n %4] mod100: [n %100] mod400: [n %400] )
Rules?
goal directed reasoning
- 1. IF (wantDays year: n )
- THEN REMOVE 1
- ADD (year mod4: [n %4] mod100: [n %100] mod400: [n %400] )
- 2. IF (year mod400: 0 )
- THEN REMOVE 1
- ADD (hasDays days: 366 )
- 3. IF (year mod100: 0 mod400: {= 0} )
- THEN REMOVE 1
- ADD (hasDays days: 365 )
- 4. IF (year mod4: 0 mod100: {= 0} )
- THEN REMOVE 1
- ADD (hasDays days: 366 )
- 5. IF (year mod4: {= 0} )
- THEN REMOVE 1
- ADD (hasDays days: 365 )
-
modulo
1%3
2%3
3%3
4%3
1%4
2%4
3%4
4%4
the modulo operation finds the remainder after division of one number by another
- 1%3 = 1
- 2%3 = 2
- 3%3 = 0
- 4%3 = 1
- 1%4 = 1
- 2%4 = 2
- 3%4 = 3
- 4%4 = 0
-
production system conflict resolution
when multiple rules are applicable simultaneously
- several strategies
- Presentation Order
- Simply the order in which the rules appear in the program-code. A programmer may exploit this for computational control.
- Specificity of conditions
- CondA is more specific than CondB when the set of WMEs satisfying CondA is a subset of those satisfying CondB. High specificity takes precedence
- Recency
- a. Rules satisfied by recent WMEs take precedence
- b. Recently used rules are deferred.
- Refractoriness
- Avoid/defer re-applying a rule on the same values. Blocks looping.
- Combination of the above
- Sift through multiple strategies in a specified order
-
rete network
precompiled network of tests to improve efficiency by avoiding multiple testing of shared conditions
- a-nodes: basic tests
- type=person, home=toronto, age<14
- b-nodes: constraints on variables
- Derives from variables occurring in multiple conditions
- leaf-nodes: rules
- The path leading to a leaf-node corresponds to the antecedent of the rule.
-
recursive
recursion
- recursive
- call same function again until you reach (base case), call function within a function
- recursion
- chain of operations
in recursion the program needs to keep track of the multiplications to be performed later
depth serach
-
iterative
- loops through the same function on one level
- breadth first
doesnt build chain, only keeps track of current values
-
construct a rete system for the following production system
-
- Initial world model:
- (group id:1 color: grey size:1)
- (group id:2 color: black size:1)
- (group id:3 color: black size:1)
- (group id:4 color: grey size:1)
- …
- (group id: 12 colour: white size:1)
- (numberOfGroups n: 12)
- rules:
- if (group id: M colour:C size:H1)
- (group id: N colour:C size:H2)
- N≠M %< would always keep the smallest id, but inefficient
- (numberOfGroups n:X)
- Then
- Remove 1
- Modify 2 (size H1+H2)
- Modify 4 (n: X-1)
-
advantages to production systems
- ■ modularity: In a production rule framework, each rule works independently of the others. This allows new rules to be added or old rules to be removed incrementally in a relatively easy fashion. This is especially useful for knowledge acquisition and for debugging.
- ■ fine-grained control: Production systems have a very simple control structure. There are no complex goal or control stacks hidden in the implementation, among other things.
- ■ transparency: Because rules are usually derived from expert knowledge or observation of expert behavior, they tend to use terminology that humans can resonate with.
-
FRAME FORMALISM
individual frames
generic frames
individual frames, used to represent single objects, and generic frames, used to represent categories or classes of objects.
olympics example
-
Olympic Assistent
Knowledge Base
Frames and Slot-names
- (Athlete
- <:IS-A Person>
- <:Name text>
- <:Participates Event>
- <:Heat NextHeat>
- <:Nationality Country> )
- (Country
- <:Song NationalAnthem>)
- (Event
- <:IS-A OL>
- <:EventName text>
- <:EventDate Date>
- <:HeatTime Time>
- <:Contestant set_of Athlete>
- <:has Location>
- <:Winner Athlete>
- <:Looser Athlete>
- <:Final Event>
- <:MedalCeremony Event>
- <:Heat NonNegativeNumber>)
- (OL
- <:StartingDate date>
- <:Events set_of Event>)
OR
- (Heat
- <:IS-A Event>
- <:Location Field>
- <:Competitor1 Athlete>
- <:Competitor2 Athlete>
- <:Winner Athlete>
- <:PrevEvent Heat>
- ...)
- <Final
- <:IS-A Heat>
- <:SemiFinal1 Heat>
- <:SemiFinal2 Heat>
- <:Competitor1
- [IF-ADDED
- {
- return SemiFinal1:Winner;
- }
- ]>
...same for competitor2 and find location
- (MedalCeremony
- <:IS-A Event>
- <:PrevEvent Final> // A medal ceremony must follow a final
- <:Music [IF-ADDED
- {
- return self:PrevEvent:Winner:Nationality:Anthem;
- }
- ]>
- <:Gold [IF-ADDED
- {
- return self:PrevEvent:Winner;
- }
- ]>
-
Olympic Assistent
IF-ADDED or IF-NEEDED procedures
- (Event
- <:Location Location>
- <:TimeSlot [IF-NEEDED
- { if(PrevEvent == null)
- return 1;
- else
- return PrevEvent:TimeSlot + 1;
- }]>
- <:PrevEvent Event>
- )
- <:Contestant set_of
- [IF-NEEDED
- // NextHeat is the next event that the contestant / athlete participates in, gets the location of the heat
- // EventDate is the same as StartingDate of the OL and after each event +1, goes to next day
- // Assume that there exists a procedure for getLocation based on the heat, assistent can find a free local
- // getAvailableTime returns the time of the heat based on the location and date
- {let Heat ← SELF:NextHeat;
- let EventDate ← StartingDate + SELF:NextHeat;
- let Location ← getLocation(heat);
- SELF:NextHeat ← SELF:NextHeat + 1
- HeatTime ← getAvailableTime(location, date)} ] >
-
Olympic Games
Examples of individual frames
- (semi-final1
- <:INSTANCE-OF Heat>
- <:Competitor1 arne>
- <:Competitor2 chang>
- <:Location firstField...)
- (Athlete1
- <:INSTANCE-OF Athlete>
- <:Name Anna>
- // An Event can change, first it may be a boxing event, then a final event, then a medal ceremony event
- <:Participates Boxing>
- // A Heat can change
- <:Heat 1>
- <:Nationality Canada>)
- // ATHLETES
- (usain
- <:INSTANCE-OF Athlete>
- <:Nationality iraq>
- ...)
-
Recall the royal family
Object Oriented Representation
generic frames for
ROYAL, FATHER, MOTHER
procedure to check if royal›
‹
Individual Frames
- (kingHarald
- <:INSTANCE-OF Royal>
- <:father kingOlav>
- <:mother princessMärtha>
- <:spouse Sonja>
- <:children {princeHaakonMagnus, princessMärthaLouise}>
- )
- (MetteMarit
- <:INSTANCE-OF Person>
- <:spouse princeHaakonMagnus>
- <:children {princessIngridAleksandra, princeSverreMagnus}>
- )
-
It is possible to extend the description logic, ?ℒ, from the book as following:
By adding concept-forming operators, like
[OR d1 d2] “either concept d1 or concept d2 (can be both)”
[NOT d] “a complement of concept d”
Give an interpretation for the concept-forming operators OR and NOT respectively.
- I [ [NOT d] ] = ¬ I [d];
- I [ [OR d1 d2] ] = I [d1] ∪ I [d2].
-
?ℒ extended with OR and NOT, and use it to formalize the following concepts:
A parent is a mother or father.
(Parent ≐ [OR Mother Father])
-
?ℒ extended with OR and NOT, and use it to formalize the following concepts:
If John and Jane are someone’s friends, then Tony is not a friend.
- I did not need to include Person after AND since it could be implied that Someone is belonging
- to the general set of Thing and since Person is not included in the statement above.
- (Someone ≐ [AND Person
- [FILLS :friend john]
- [FILLS :friend jane] ] )
- (if Someone then [NOT
- [FILLS :friend tony] ] )
- a -> b = -a v b ekvivalensen, dvs,
- [or
- [not [and [fill :friend john] [fill :friend jane]]]
- [not [fill :friend tony]]
- ]
-
?ℒ extended with OR and NOT, and use it to formalize the following concepts:
Not all birds can fly.
- Which written would be ¬(∀x Bird(x) → Fly(x))
- Which is equivalent to (∃x Bird(x) ∧ ¬Fly(x))
- So I have written, there exists at least one species of bird that cannot fly. More specifically does
- not have the movement fly. A movement could be walk, eat, fly, ect.
- [AND Bird
- [EXISTS 1 :species]
- [NOT
- [FILLS :movement fly] ] ]
-
?ℒ extended with OR and NOT, and use it to formalize the following concepts:
An animal that eats only fish, but not Nemo.
- [AND Animal
- [FILLS :eat fish]
- [NOT
- [FILLS :eat nemo]
- [NOT
- [FILLS :eat nonFish]]] ]
-
1.3 - State whether the sentence ColderThan(milan, moscow) is minimally entailed and why.
KB = { NorthOf(milan, glasgow), NorthOf(milan, london), NorthOf(milan, moscow), glasgow ≠ london, london ≠ moscow, glasgow ≠ moscow, ¬ColderThan(milan, glasgow) ∨ ¬ColderThan(milan, london), ∀x(NorthOf(milan, x) ∧ ¬Ab(x) ⊃ ColderThan(milan, x)) }
- Definition Minimal Entailment
- KB ⊨ ≤ ? iff either ℑ ⊨ ? or there is an ℑ’ such that ℑ’ < ℑ and ℑ’ ⊨ KB
Sentence: For all cases of x (a city) NorthOf milan, where x is not abnormal, x is ColderThan milan.
- Our sentence says that for all x, imply x is colder than milan, however only glasgow or london can be colder than the other. Given extension I(Ab), we have either I(glasgow) or I(london) but not both. For both interpretations I(moscow) isn’t in I(Ab), meaning it is not abnormal.
- For both interpretations, (I(milan), I(moscow)) holds true for I(NorthOf), since KB = {NorthOf(milan, moscow)}. Therefore, the sentence ColderThan(milan, moscow) is minimally entailed.
OR
- KB ⊭ ColderThan(milan, moscow) however KB ⊨≤ ColderThan(milan, moscow).
- Because, if ℑ ⊨ KB but ℑ ⊭ ColderThan(milan, moscow) then ℑ ⊨ Ab(moscow).
- However, by using the definition above we can do the following:
- Since our goal is to minimize normality it is then possible to include ℑ’ ⊨ KB and therefore ℑ’ ⊨ ¬Ab(moscow) since ℑ’ < ℑ.
- This inference tells us that moscow is normal or rather given extension I(Ab), I(moscow) fulfills the requirement for I(¬Ab). Therefore, the sentence ColderThan(milan, moscow) is minimally entailed.
-
Definition Minimal Entailment
KB ⊨ ≤ ? iff either ℑ ⊨ ? or there is an ℑ’ such that ℑ’ < ℑ and ℑ’ ⊨ KB
minimal entailment considers not all models of the KB but only those where the set of exceptions is made as small as possible. only need 1 AB for each rule. notA or notB === A and B -> false
|
|