Transcript GOLOG David Mui EEL6938

GOLOG
David Mui
EEL6938
Outline






Introduction
Situational Calculus
GOLOG
Personal Banking Assistant Using GOLOG
ConGOLOG – GOLOG variant
Conclusion
Introduction

Computers System


Embedded in complex environments
Software for such systems does not maintain explicit
model of the world


Designers/Programmers



Users and designers of the system have a general mental
model of the environment
Problematic because they need to reconstruct the
model
Difficult to extend because of high level abstraction
Solution: GOLOG
GOLOG

What is GOLOG?





An Extension of situational calculus


Logic Programming Language for Dynamic Domains
Maintains explicit model of environment domain
Can be queried, reasoned at runtime
Based on theory of actions and preconditions
First,Second order logic
Applications of GOLOG?




Robotics
Artificial Intelligence
Mechanical Devices
Modeling and Simulation
Situational Calculus

Logic Formalism designed for representing dynamic
domains



First Order/Second Order logic formulae
Actions performed in the world
Fluent describe the world state


Situations





Can be thought of as properties of the world
Finite sequence of actions
Changes to the environment result in Actions.
Actions can be parametrized
Sequence of actions is described as a situation
S0 defined as initial situation constant (no action or
situation)
Situational Calculus Cont.

Binary function do:


do(a,s), denotes successor situation based on “a”
(action) on “s” (situation), (i.e. the new situation)
Example:


pickup(A ,S0)
do(putdown(A) ,do(walk(L), do(pickup(A) ,S0)))
Situational Calculus Cont.



Properties of the environment or world can be
seen as fluents
Relational Fluents
 Truth values that may change
 is_carrying(robot, item, s)
Functional Fluents
 Functions that take the situation as their final
argument
 Returns a situation dependent value
 loc(robot, s)
Creating Axioms from Actions



Actions and effects of the actions are axiomatized
Actions have preconditions.
World Dynamics are specified by effect axioms
Frame Problem


To define a dynamic world it requires more than
just action preconditions and effect axioms
Frame Axioms




Defines action invariants of the domain
Could be a vast number of frame axiom in a domain
Fluents unaffected by the action
Example:

If robot picks up an object location does not change.
Solution to the Frame Problem

Generate Successor state Axiom



Collect all effect axioms from fluent and make a
completeness assumption
Assume it specifies all possibilities the fluent may
change
Transform effect axioms to generate successor state
axiom of given fluent
Situational Calculus, Cont.

A domain is defined by the following theory:

Axioms defining the world in different situations

Action preconditions

Successor state axioms

Foundational axioms
Complex Actions in GOLOG

Situational Calculus methods described in
previous slides can not handle complex actions
and reasoning




Procedures
Loops
Nondeterministic actions
Need to define complex actions with additional
symbols
Complex Actions, cont.

Define Complex Actions using extralogical symbols
(e.g., while, if, etc.)

Extralogical expressions are macros that expand into formulas

Do(δ, s, s`) is the basic abbreviation in the GOLOG language,
where δ is a complex action expression, for complex
operations

Do(δ, s, s`) means that executing δ (complex action) in
situation “s” has s` as a terminating situation
Complex Actions, cont.
1.Primitive Actions
2. Test Actions
3. Sequence
Complex Actions, cont.
4. Nondeterministic choice of two actions
5. Nondeterministic choice of two arguments
6. Nondeterministic Iterations
Complex Actions, cont.

Conditional and loops definition in GOLOG

Procedures difficult to define in GOLOG

No easy way of macro expansion on recursive
procedure calls to itself
Complex Actions, cont.


Create auxiliary macro definition: For any
predicate symbol P of arity n+2 taking a pair of
situation arguments
Define a semantic for procedures utilizing
recursive calls
GOLOG in a Nutshell



GOLOG programs are executed uses a theorem prover
User supplies, axioms, successor state axioms, initial situation
condition of domain, and GOLOG program describing agent
behaviour
Execution of program gives:
Example GOLOG


Elevator Controller Example
Primitive Actions






Up(n): move the elevator to a floor n
Down(n): move the elevator down to a floor n
Turnoff: turn off call button n
Open: open elevator door
Close: close the elevator door
Fluents



CurrentFloor(s) = n, in situation s, the elevator is at
floor n
On(n,s), in situation s call button n is on
NextFloor(n,s) = in situation s the next floor (n)
Example, cont.

Primitive Action Preconditions

Successor State Axiom
Example, cont.


One of the possible fluents
Elevator GOLOG Procedures
Example, cont.

Theorem proving task

Successful Execution of GOLOG program

Returns the following to elevator hardware control
system
Personal Banking Assistant Using
GOLOG

Personal Banking Assistant (PBA)





Assists users in personal banking over computer
networks
Perform transactions based on certain actions,
preconditions, and situations
Collection of GOLOG agents that interact
Over 2000 lines of GOLOG Code
Currently implemented in simulated financial
environment
System Components

Personal Banking Assistant Agents


Bank Agents


Conducts fund transfers between different bank
institutions
Router Agents


Perform backend bank operations on accounts
Transfer Facilitator Agents


User interface, performs actions directed by user, and
monitors for certain situations
Performs network operations/maintenance
Automated Teller Agents

Provides ATM interface to bank agents
System Diagram
PBA Fluents

Fluents used by the PBA to model the world:





USERACCOUNT(type, bank, account, balance,
lastUpdate, rateOfReturn, moveFunds, minBalance,
penalty, refreshRate, s)
Monitor(type, bank, account, limit, lowerOrHigher,
priority, response, monID, s)
ALERT(alertMessage, maxPriority, monID, s)
ALERTACKNOLWEDGED(monID,s)
WAITINGUPDATE(bank, account, s)
PBA Primitive Actions

SENDMESSAGE(method, recipient, message)

STARTWAITINGUPDT(bank, account)

STOPWAITINGUPDT(bank,account)

CREATEALERT(message, maxPriority, monID)

SENDALERT(priority, message, medium, monID)
PBA, cont.

ControlPBA



Requests balance updates for accounts
Process messages
Send out alert messages to users
PBA, cont.

RefreshMonitoredAccts



Request balance updates for accounts
Process new messages
Send out new messages to users
PBA, cont.

HandleCommunications Procedure



Main message handling loop
Reads message from port and dispatches to appropriate
action
GenerateAlerts Procedure


Directs agent to monitor triggers defined by user
Alerts the user
PBA Results

Pros:


GOLOG capable of building useful applications
Provides structure for the programmer



Preconditions, successor state axioms
Encourages a layered design
Cons:

Certain operations are tricky to accomplish





Performing arithmetic
Assigning a value to a variable
Limited debugging tools
Lack of standard libraries
Lack of event driven reactive behaviors
ConGOLOG
ConGOLOG

Extended version of GOLOG that incorporates
concurrency




Concurrent processes with different priorities
High level interrupts
Arbitrary actions
ConGolog differs from other formal models of concurrency
 Allows incomplete information about the environment
 Allows primitive actions to affect the environment in a complex
way and such changes to the environment can affect the
execution of the remainder of the program
New Semantic for Concurrency


ConGOLOG adopts a transition semantic
Trans Predicate


Defines a transition relation between two processes
Final Predicate


Final process
Determines when process is completed
Trans Axioms
1. Empty Program
2. Primitive Action
3. Wait/Test Actions
New Concurrency Constructs

Constructs to handle concurrent programming in
ConGOLOG
Other GOLOG Variants

CcGOLOG


GOLEX



Incorporates continous change and event driven
behavior
Execution and monitoring system, distributed control
software
Autonomous mobile robots, sensing and interaction
IndiGOLOG

Incremental Interpreter for high level programs
involving nondeterminisim and sensing actions
Conclusion



Logic programming for dynamic domains such as
robotics, intelligent software agents, and modeling
and simulations
GOLOG is based on situational calculus, utilizing
first/second order logic and formal theory of
actions
Variants (ccGOLOG, ConGOLOG…etc.)

To solve weakness such as concurrency, event driven,
sensing
References


Hector J. Levesque, Raymond Reiter, Yves
Lesperance, Fngzhen Lin, and Richard B. Scherl.
GOLOG: A logic programming language for
dynamic domains. To appear in the Journal of
Logic Programming, special issue on Reasoning
about Action and Change, 1996.
Yves Lesperance, Hector J. Levesque, and Shane J.
Ruman. An Experiment in Using GOLOG to Build
a Personal Banking Assistant. To Appear in
Intelligent Agent Systems: Theoretical and
Practical Issues, 1997.
References, cont.


Giuseppe De Giacomo, Yves Lespérance, and
Hector Levesque. ConGolog, a concurrent
programming language based on the situation
calculus. Artificial Intelligence, 121(1-2):109-169,
2000.
Yves Lespérance, Todd G. Kelly, John
Mylopoulos, and Eric S.K. Yu. Modeling dynamic
domains with ConGolog. In Proceedings of
CAiSE-99, Heidelberg, Germany, June 1999.