Transcript powerpoint

Artificial Intelligence and Lisp #13
1. Examples of Current AI Systems
2. Cognitive Agent Architecture
3. Lisp Software Design Methods
4. Remaining Topics on Lisp
5. Towards the End of the Course
1. Examples of Current A.I. Systems
•
From the list of contributions at 2009 IAAI conference (Innovative
Applications of Artificial Intelligence)
•
Developing an End-to-End Planning Application from a Timeline
Representation Framework. Amedeo Cesta, Gabriella Cortellessa,
Simone Fratini, Angelo Oddi
•
An Emergency Landing Planner for Damaged AircraftNicolas
Meuleau, Christian Plaunt, David Smith, Tristan Smith
•
Task Assistant: Personalized Task Management for Military
Environments. Bart Peintner, Jason Dinger, Andres Rodriguez, Karen
Myers
•
Automated Critique of Sketched Mechanisms. Jon Wetzel, Ken
Forbus
•
An Ensemble Learning and Problem Solving Architecture for
Airspace Management. Xiaoqin Zhang, Sungwook Yoon, Jinhong
Guo , Prasad Tadepalli , Elizabeth Whitaker, Diana Spears, Gerald
DeJong, Victor Lesser, Deborah McGuinness, Zhexuan Song
•
Using AI to Solve Inspection Scheduling Problem for a Buying Office.
Xianhao Zhou, Songshan Guo, CHAN HOU CHE, Brenda Cheang,
Andrew Lim, Hubert Kreuter, Janet Chow
2. Cognitive Agent Architecture
•
Review of SOAR architecture (discussed in an earlier
lecture)
•
Three-level architecture
•
Detailed three-level architecture
•
Interpretation feedback in architecture
•
Two-tower architecture
SOAR Architecture (early 1980's)
•
A classical approach (although preceded by McCarthy's
advise taker proposal)
•
Sense-Assess-Decide-Act cycle, with possibility of
recursion
•
Objection 1a: fails to handle evolving input and actions.
(Not fair if the proposal is interpreted reasonably)
•
Objection 1b: not a natural representation of evolving
input and actions.
Three-Level Architecture (around 1990)
Deliberative layer
Reactive layer
Process layer
SOAR Architecture (early 1980's)
•
A classical approach (although preceded by McCarthy's
advise taker proposal)
•
Sense-Assess-Decide-Act cycle, with possibility of
recursion
•
Objection 1: fails to handle evolving input and actions, or
not a natural representation for these
•
Objection 2: its top-down structure of rational behavior is
not psychologically adequate
•
Recommended reading: Malcolm Gladwell: Blink, the
Power of Thinking without Thinking. 2005; Penguin
books, 2006
One Detailed Three-level Architecture
Recognition
of objectives
Exception
rules
Observation State
World
Management of
Objectives
Anticipation
plan
Performance State
incl. next action
Passive plan
Critique
proposed
action
Execute
decided
actions
Plug-ins in Detailed 3-level Architecture
•
From world to observation state
•
From observation state to performance state (including
proposed next action) using exception rules
•
From performance state: critique of proposed action
•
Execution of accepted action
•
From observation state to objectives using a recognizer
•
Management of objectives: develop plan, cost-benefit
evaluation of plan, maintain priority order, update objectives
structure
•
Adoption of objective-based plan
•
Obtain plan when no objective has been selected
Components in Detailed 3-level Architecture
•
From world to observation state: decision tree for classifying the
situation; causal nets or theorem-proving for constructing
explanations and extrapolating consequences
•
From observation state to performance state (including proposed
next action) using exception rules: condition-action rules or decision
tree
•
From performance state, critique of proposed action: predictions
using a theorem-proving technique e.g. resolution, or simulation
•
Execution of accepted action: precondition resolution as in lab2b
•
From observation state to objectives using a recognizer: conditionaction rules or a decision tree
•
Management of objectives: develop plan, cost-benefit evaluation of
plan, maintain priority order, update objectives structure: action
planning techniques; ordinary software techniques
•
Adoption of objective-based plan: conventional
•
Obtain plan when no objective has been selected: use a default
Generalized action and plan concepts
•
Techniques from earlier lectures apply for a single agent,
sequential plans, single-timestep actions, no spontaneous
changes. More general approach is needed.
•
Durative actions: Recommend to maintain a distinction between
direct (momentary) and durative actions. Each durative action is
initiated by a direct action.
•
Condition-action rules (previous slide) use direct actions for
updating observation state and performance state
•
Useful technique: use an anticipation-plan which specifies
expected forthcoming conditions, and the actions that are to
follow then. These actions should be operations on the
performance state.
Computer Learning
•
In general, learning is a process where an agent changes
some aspects of its own structure in response to previous
experience
•
This may be applied e.g. to the structure of a decision tree
and the parameters in it, or to the set of clauses in a theoremprover, or to the set of restrictions in a SAT solver
•
It is not so fruitful to discuss learning in the abstract – one
must first have some of these structures where learning can
occur
•
Usually, learning presumes that you have a set of inputs
where the correct answers are known. However there are
exceptions
•
In the normal case, standard practice to separate between a
training set and a verification set of cases.
Example of Interpretation Feedback
Action
Video
camera
Bandwidth
reduction
Image
Analysis
Cognitive
interpretation
Revised Detailed Three-level Architecture
Recognition
of objectives
Management of
Objectives
Exception
rules
Observation State
Anticipation
plan
Performance State
incl. next action
Sensed State
World
Passive plan
Critique
proposed
action
Execute
decided
actions
Two-Tower Architecture
(Nils Nilsson et al., Stanford)
Sensory
Tower
Effectuation
Tower
3. Lisp Software Design Methods
•
Incremental style of working
•
Spectrum from procedural to declarative – make good
use of the declarative side
•
Self-administration of software
•
Engines and scripts – Lisp as a high-level
implementation language
Important Software Techniques for
the Self-administration of Software
•
Program components should be data objects (entities) and
their contents should be accessible for processing
•
All data objects should have a textual representation
•
Catalogs of program components should be explicitly
available
•
It shall be possible to assign function definitions or other
pieces of programs as properties (attributes) of data objects
(entities, in the case of Leonardo)
•
It is desirable to have a systematic way of forming composite
entities
Conventional (vs Lisp-style) applications
Application
Queries
Library modules
Database
system
C++, Java, etc
Typical AI System Using Lisp
Application
Scripts/
Scripts
Knowledgebase
Library modules
Engine
C++, Java, etc
Engine
Lisp
Example
Application
Causal nets and decision
trees for the application
Lab3: interpreter for
causal nets and
decision trees
Scripts
Engine
Lisp
Other Example
Dialog
Engine
Dialog Scripts
Application
Other engines
Lisp
Examples of engines and
their scripting languages
•
Action planner (e.g. POP); planning domain description
language (PDDL)
•
Resolution theorem prover; clause representation of
predicate logic
•
SAT solver
•
Natural-language analysis and generation; context-free
grammar (= BNF) and additional grammatical rules
•
Diagnosis engine; causal nets combined with decision
trees
•
Constraint logic programming as an engine built on top
of logic programming (prolog)
•
Prolog as an engine built on top of a Lisp system
Scripting languages =
special-purpose languages
•
The designer of a conventional programming language
usually wishes it to be general purpose
•
Target for a special-purpose language: a domain that is
conceptually restricted but which has a large usage
•
Being conceptually restricted makes it possible to have a
concise language and effective computational support
•
This requires that the scripting language is only used for
one part of a larger system, and that its use can be
efficiently integrated with the other parts of the system
•
This can best be achieved if the scripting language(s)
can be tightly connected with the host programming
language
Implementating a High-level Language or
Scripting Language in Lisp
•
1. Design the language
•
2. Design a parser and an interpreter for the language
•
3. Design additional services, algorithms that are oriented towards
the application area, etc.
•
Example: Planning Domain Definition Language (PDDL)
•
Same language used by several actual systems
•
Parser for the language: convert the textual language to an
appropriate internal representation in the program
•
Interpreter, in this case: a planning algorithm
•
Implementation is facilitated by using an S-expression syntax.
•
Integration with other systems is facilitated by common data
structure
Writing Programs in Lisp
•
Priorities:
•
The implementation of special-purpose or scripting
languages; not the implementation of entire applications
•
The implementation of algorithms that can operate on
expressions in those languages (internalized)
•
Easy integration with other, similar subsystems
•
Capability of invoking subsystems written in other
programming languages
4. Remaining Topics, a: Lisp
•
..
Garbage Collection
•
The technique of garbage collection was invented in Lisp
very early (1959). It was adopted by Simula (mid-60's)
but resisted in most programming languages until Java
adopted it in the 1990's.
•
Basic idea: let the cons operation allocate new cells from
a “free list”. When this list has been exhausted, then
scan memory and reclaim unused cells.
•
Standard techniques: (1) mark used cells, then reclaim
unused cells, (2) copy entire structure between two
halves of memory, (3) count incoming pointers, (4)
sophisticated schemes
•
Problem with simple techniques: causes the system to
“go to sleep” from time to time
Development History and Variants
•
Initially: Lisp 1.5, developed at MIT
•
Divergence between MacLisp (MIT, Stanford) and InterLisp
(BBN, Xerox PARC)
•
DARPA enforced a standard (CommonLisp) mostly based on
MacLisp. InterLisp died.
•
CommonLisp was criticized for being too complex; other
variants were proposed in particular in Europe, but did not
catch on
•
Scheme was developed at MIT, Lisp-like and with a simpler
design
•
Functional programming languages: puristic design
•
Tendency in Lisp systems has been to admit a rich range of
facilities, at the expense of purism
Impact
•
Lisp has always met with resistance in mainstream
computing due to its approach to the syntax of programs,
written as S-expressions
•
Characteristic properties of Lisp have been adopted in
other languages: recursion, garbage collection, closures,
etc.
•
Programming environments were pioneered in InterLisp
•
Some aspects of Lisp have still not been adopted in
conventional languages, esp. procedural attachment
•
Languages such as Python inherit many of Lisp's
characteristic features
•
Leonardo is essentially Lisp with a somewhat richer
range of basic datastructures and syntax for them, but
without full programming-language capability
Remaining labs
•
Free choice between lab4b and lab5b - only one of them is
required
•
Lab4b integrates the facilities of the earlier labs, using a
simple version of the “detailed three-level architecture” shown
here
•
Lab5b consists of writing a small Lisp program, somewhat
bigger than the exercises in lab5a. Instructions on the
webpage; no automatic check for correctness
•
Lab5b available very soon
•
Lab4b available early next week
•
Even if you choose lab5b, it is recommended to just read the
instructions for lab4b in order to get a concrete example of
the agent architecture
Additional Lisp Activities
•
If there is an interest for it, we can organize a small “Lisp
study circle” early next year (January or March)
•
Alternative exam (less AI, more Lisp) can be arranged
after that circle
•
Please contact me if you are interested in such an
arrangement
Exam
•
Three weeks from tomorrow (22.12 at 14.00 - 18.00)
•
Will be different from exams of earlier years, since the course
has been reorganized
•
Examples of exam questions will be shown and discussed on
Wednesday morning