Transcript Artificial Intelligence - Computer Science

Artificial Intelligence
Dr. Paul Wagner
Department of Computer Science
University of Wisconsin – Eau Claire
Messages


Artificial Intelligence (AI) is an
interesting sub-field of computer
science that provides many
contributions to the overall field
CS 420, as the AI course at UWEC, is a
good opportunity to begin to explore
these issues
Outline


Overview
AI Topics
–
–
–
–
–
–
–
–


Knowledge representation
Problem solving and search space manipulation
Planning
Learning
Communicating
Uncertainty
Intelligent agents
Robotics
AI Languages
MICS Robot Contest Video
Overview of Artificial
Intelligence

Definitions – four
major combinations
– Based on thinking
or acting
– Based on activity
like humans or
performed in
rational way
Systems
Systems
that think that think
like
rationally
humans
Systems
that act
like
humans
Systems
that act
rationally
AI Definitions

Acting Humanly
– Turing Test – computer passes test if a
human interrogator asking written
questions can distinguish written answers
from computer or human
– Computer needs:
Natural language processing
 Knowledge representation
 Automated reasoning
 Machine learning

AI Definitions (2)
– Total Turing Test – includes video
component (to test subject’s perceptual
abilities) and opportunity to pass physical
objects to subject
– Computer also needs:
Computer vision
 Robotics

AI Definitions (3)

Thinking Humanly
– Cognitive Modeling approach to AI
– Involves crossover between computer
science and psychology – cognitive
science
– Areas of interest
Cognitive models
 Neural networks

AI Definitions (4)

Thinking Rationally
– “Laws of thought” approach to AI
– Goal: solve any problem based on logical
manipulation
– Problems


Difficult to represent certain types of knowledge (e.g.
common sense, informal knowledge)
Difference between solving problems in principle and in
practice
– E.g. computational limits
AI Definitions (4)

Acting Rationally
– “Design a rational agent” approach to AI
– Advantages over logic approach
Logic is only one tool or many that can be
used to design rational agent
 Scientific advances can provide more tools for
developing better agents

Knowledge
Representation



How to represent information?
Generally, we use some sort of tree, grid or
network
Options
– OO programming languages: classes/objects
– Relational database system:
tables/rows/columns

Problem
– The world is more varied, with many types of
things to represent
Knowledge
Representation (2)

Abstract Objects
– Sets
– Sentences
– Measurements



Times
Weights
Generalized Events
–
–
–
–
Intervals
Places
Physical Objects
Processes
Knowledge
Representation (3)

Some things are very difficult to represent
– Common sense

See http://www.cyc.com/
– Combinations of multiple types

Issues of:
–
–
–
–

Type
Scale
Granularity
Combination
Other Questions
– How to distinguish knowledge and belief?
– What is the best way to reason with this information?
Problem Solving and Search
Space Manipulation

Many Algorithmic Approaches to
Problem Solving
– Depth-First Search
– Breadth-First Search

Variations
– Depth-Limited Search
– Iterative Deepening Depth-First Search
– Bi-directional Search
Problem Solving and Search
Space Manipulation (2)

Smarter Search
– Greedy best-first search
– A* search (combine costs of path so far
plus path from current node to goal)
– Memory-bounded heuristic search

Heuristic – means of estimating a
measurement such as cost of search
Problem Solving and Search
Space Manipulation (3)

Issues
– Avoiding repeated search
– Searching with partial information
Problem Solving and Search
Space Manipulation (4)

Adversarial Search
– E.g. games and game trees
– Minimax algorithm
– Alpha-Beta pruning
Problem Solving and Search
Space Manipulation (5)

Applications of Problem Solving
– Expert Systems

Approximating the functionality of an absent
human expert
– Robotics

Encountering unexpected obstacles
Planning

Many types of
problems
– “Blocks world”
– Getting yourself from
Eau Claire to the AAAI
conference in Boston
– Changing a flat tire
– Completing all of your
projects at the end of
the semester
– Developing a large
software application
Planning (2)

Approaches
– State-based search
– Partial-order planning
– Planning graphs

Issues
– Time
– Scheduling
– Resources
Learning


Definition - Building on current knowledge
by using experience to improve a system
Various approaches
– Supervised/unsupervised/reinforcement

Forms of learning algorithms
– Inductive logic

Example: given a set of point, approximate a line
– Decision tree (set of questions, act differently
depending on answer)
Learning (2)

Issues
– Computational Learning Theory

Intersection of theoretical CS, AI, statistics
– How many examples do you need?
Communicating

Major issue - Natural language processing
– Many issues



Syntax
Semantics
Context
– Steps





Perception
Parsing
Analysis
Disambiguation
Incorporation
Uncertainty

Much knowledge is not absolute
– Boundary between knowledge and belief is gray

Techniques for dealing with uncertainty
–
–
–
–
–

Probabilistic reasoning
Probabilistic reasoning over time
Fuzzy sets / fuzzy logic
Simple decision-making (evaluating utility)
Complex decision-making (taking ability to reevaluate into
account)
Applications
– Expert systems
Intelligent Agents

Everything we’ve talked about can be
viewed in terms of embedding
intelligence within an agent
– Software system
– Machine with embedded software
– Robot
Intelligent Agents (2)

Issues for agents
–
–
–
–

Limitations on memory
Perceiving its environment
Working with other agents
Affecting its environment (through actuators)
Processes
– Simple – based on rules
– Complex – based on multiple pieces of logic,
dealing with uncertainty
Robotics


Field encompassing elements of computer
science/AI, engineering, physical systems
Issues
– Many that we’ve discussed, plus:
– Perception
– Actuation

Recent successes
– Worker bots (e.g. floor cleaners)
– Intelligent navigation (DARPA vehicle contest)

Test environments
– Lego Mindstorms
– Other robot packages or custom systems
AI Languages

Scheme / LISP
– Functional
– Simple knowledge representation (list)
– Easy to apply functionality to represented elements

Prolog
– Logic-based
– Facts and rules easily represented
– Built-in search engine

Specialized languages
– Rule languages (e.g. CLIPS)
– Planning languages (e.g. STRIPS)
CS 420




Spring semester, about every other
year
Will be offered Spring 2007
Prerequisite: CS 330 (to get Scheme
and Prolog background)
Topics
– All of the above!
CS 420 (2)

Possible Projects
– Neural network to simulate decision
making, natural language processing
– Software development planning through
cooperating intelligent agents
– Expert system for deciding which courses
to take to complete a CS major
– Sumo robots?
MICS Robot Contest
Video

http://video.google.com/videoplay?doc
id=7851913746457357108&hl=en