Study Material for MidTerm
CIS480
[Note: Summary of chapter 6 notes is still in progress]
Here are some notes to help you as you study for the MidTerm exam.
Key Concepts & Terms Class Notes
AI the study of intelligence in order to design machines that are better able to serve humankind.
Logos-telos-teleios triad
agent entity that acts on behalf of another
robot autonomous agent
intelligent robot intelligent autonomous agent
robot autonomous agent
Key Concepts & Terms Textbook
Chapter 1:
paradigm set of assumptions or techniques which characterize an approach to a class of problems
primitives
sense
plan
act
3 main paradigms
hierarchical
reactive
hybrid
teleoperation
cognitive fatigue
simulator sickness
telepresence
semi-autonomous control
continuous assistance (shared control)
control trading
The 7 areas of AI
Nested Hierarchical controller (NHC)
NIST RCS real-time control system
Chapter 2:
2. The Hierarchical Paradigm
GPS general problem solver
Means-ends analysis
STRIPS Stanford Research Institute Problem Solver
Differences
Difference table
Reducing differences
STRIPS components
Goal state
Initial state
Operator
Difference evaluator
Preconditions
Postconditions
Add-list
Delete-list
Closed world assumption world model contains everything the robot needs to know
Open world assumption robot must function in an open world with incomplete knowledge of the world
Frame problem the result of computational complexity of updating all world information, both that which does and does not change
Advantages & disadvantages
Chapter 3:
3. Biological Foundations of the Reactive Paradigm
3.1 Overview
Moravec, Arbib, Braitenberg
Features of agent
self contained
independent
self-aware
Ethology scientific study of animal behaviors
Pioneers
reflexes lasts only for duration of stimulus
taxes oriented with respect to stimulus
fixed action patterns continue beyond duration of stimulus
How acquire behavior
born with
learn
Innate releasing mechanism (IRM) specific stimulus which releases (triggers)
stereotypical pattern of action
releaser latch or Boolean variable; acts as control signal to activate behavior
motivation internal releaser
compound releaser comprised of more than one stimulus all of which must
be present
implicit chaining completion of one behavior is trigger to next
implicit sequence created by implicit chaining
explicit sequence sequence specified by program code
3.3.2 Concurrent behaviors
Result of multiple release of behaviors:
equilibrium behaviors balance each other out
dominance winner take all
cancellation each behavior prevents the other
Perception 2 functions
release
guide
Brooks (or Gibson) the world is its own best representation
affordance perceivable potentiality for an action
direct perception
recogntion
3.5 Schema Theory
Schema generic template for doing some activity
Consists of
knowledge how
computational process
Behavior
motor schema
perceptual schema
releaser
Programming principles
Unresolved issues
conflicts between concurrent behaviors
memory
knowl. rep.
learn new
Chapter 4:
4. The Reactive Paradigm
Horizontal decomposition
hierarchical architecture
sense, then plan, then act
Vertical decomposition
reactive systems
close coupling of sensing & acting
behaviors the basic building blocks
pioneers
Attributes
Features
Five main characteristics
4.3 Subsumption Architecture
Subsumption architecture
Rodney Brooks
First to
4 aspects
Summary
behavior is tight coupling of sensing & acting
schema-like modules grouped into layers of competence (abstract behaviors)
higher layers may subsume lower ones
design of layers & component behaviors more art than science
behaviors are released by presence of stimuli
solves frame problem by eliminating need to model world
behaviors do not remember past
perception is largely direct, using affordances
releaser for behavior is usually percept for guiding motor schema
perception is ego-centric & distributed
Potential field architecture
motor action of behavior must be represented as potential field
potential field array (of field) of vectors
vector tuple (m,d) where
m = magnitude
d = direction
of force being exerted
world is a map [(x,y) grid] of space
array elements are one square unit of space
perceivable objects exert force field on surrounding space
robot is a particle within the force field
force fields are ego-centric (as is also reactive robot)
force field represents
what robot should do (motor schema)
if it perceives an object (perceptual schema)
Primitives 5 basic potential fields
uniform, perpendicular, attractive, repulsive, tangential
Magnitude profile
problem addressed
reflexivity
linear drop off
exponential drop off
fine tuning behaviors
Primitive potential field is represented by single function
Robot computes effect of potential field at every update
no memory
Potential field & behaviors
requires that all behaviors be implemented as potential fields
combines behaviors by vector summation
Problems of pF method
update rates
holonomicity
local minima
Functional cohesion every statement in a function has something directly to
do with functions purpose
Data coupling each function call takes a simple argument
result all functions are independent
Procedural cohesion code is specific to (in this case) the robot
Advantages
a continuous representation
easy to visualize space
easier to visualize robots overall behavior
easy to combine fields
can make behavioral libraries
can be parameterized
range of influence can be limited
can be extended to 3D
Disadvantages
local minima problem
Major pF points
motor schemas must be potential fields
all behaviors operate concurrently
output vectors are summed
behaviors are treated equally (not layered)
possible to have abstract behaviors (internally sequence component
behaviors)
behaviors can make varying contributions to overall action of robot
behaviors can inhibit or excite other behaviors
perception is handled by direct perception or affordances
perception can be shared by multiple behaviors
a priori knowledge can be supplied
4.5 Evaluation of Reactive Architectures
4.6 Summary
Comparison of subsumption & pF
Chapter 5:
5. Designing a Reactive Implementation
5.1 Overview
Two deficits in programming
art/ science
integrate behaviors
Addressing these deficits
object-oriented
sequence of behaviors
FSA
scripts
OOP
object consists of
data (attributes)
methods (operations)
Schema will be a class
Schema class will have optional method called coordinated control program
Coordinated control program function that coordinates any methods or
schemas in the derived class
Three classes are derived from the Schema Class
Behavior
Motor Schema
Perceptual Schema
Behavior object is storage location of percept
Note definition of behavior is recursive
Primitive behavior
Abstract behavior
Within OOP what object or construct contains releaser?
releaser is itself a perceptual schema
How is it attached to the behavior?
5.3 Steps in Designing a Reactive Behavioral System
Steps in Designing Reactive Behavioral System
Specification & analysis
Design
Implementation & unit testing
System testing
5.5 Assemblage of Behaviors
Problem how to encapsulate set of behaviors & sequencing logic into module?
use OOP schema structure to collect behaviors into abstract behavior
make coordinated control program a member of abs. behvr.
it expresses releasers for component behaviors
How to formally represent releasers? 3 common ways
FSA
scripts
skills
Key point make the world trigger or release next step
- do not rely on internal model
5.5.1 Finite state automata
Representations
Formal definition :: M = (K, S, d, s, F)
Relation of FSA to behaviors
K all the behaviors for a task
S - the releasers for each behavior in K
d - function that computes next state
s the behavior the robot starts in when turned on
F the behavior(s) the robot must reach to terminate
5.5.5 Scripts
Scripts or skills often used for abstract behaviors
Scripts
have room for improvization
sub-script to handle unexpected condition
causal chain the main sequence of events
embodies the coordination control program logic
simplify specification (FSA force designer to consider & enumerate
every possible transition)
Concepts for coordinating behaviors of robot in efficient & intuitive manner
indexing
focus-of-attention
Chapter 6:
6. Common Sensing Techniques for Reactive Robots
all sensing is behavior-specific
sensor device that measure some attribute of the world
transducer mechanism that transforms the energy associated with what is
being measured into another form of energy
Sensing
sensor observation intercepted by perceptual schema which
extracts relevant percept
which is used by motor schema
to lead to action
Classification
passive
active
Logical sensor unit of sensing or module that supplies a particular percept
Is the functional building block for perception
Behavioral sensor fusion
How sensors can be combined
redundant, complementary, coordinated
Types of sensor fusion
action-oriented sensor fusion
sensor fission
sensor fashion
Sensor suite the set of sensors used by the robot
Designing begins with assessment of type of information needed
Categories of sensing
Internal sensor data comes from robot
kinesthetic
with respect to envt.
External sensor data comes from environment
Attributes to consider for sensor
Field of view and range region covered (in degrees) & distance
Accuracy, repeatability, resolution
Responsiveness in target domain
Power consumption
Hardware reliability
Size
Interpretation reliability
Attributes to consider for entire sensor suite
Simplicity, modularity, redundancy, fault tolerance, error/failure
detection
Shaft encoder
INS
GPS
Differential GPS
Proximity sensors
sonar, infrared (IR), bump sensors, feeler sensors (whiskers)
Sonar concepts
Time of flight
Denning rings
Echo
Side lobes
Dead time
Specular reflection
Foreshortening
Cross-talk
Problems
Computer vision processing data from any modality which uses
electromagnetic spectrum and which produces an image
Pixel
Image function
CCD
MOS
Line transfer
Frame transfer
Framegrabber
6.6.2 Grayscale and color representation
Grayscale 8 bit number with 0=black & 255=white
RGB color represented as 3 color planes (axes of a cube)
color is a triple to be summed
black = (0,0,0) = 0+0+0
white = (255,255,255)
red = (255,0,0)
green = (0,255,0)
blue = (0,0,255)
Visual erosion robot moves; incidence of light changes; object appears to
erode with changes in lighting
HSI = hue, saturation, intensity a representation of color
Hue the dominant color wavelength; does not change with robots relative
position nor objects shape
saturation lack of whiteness in a color
red is saturated; pink is less saturated
Intensity (value) quantity of light received
HSV ≅HSI [see:http://www.soc.staffs.ac.uk/ccc1/ISE/VisualDataReproduction06.ppt
& http://davinci.asu.edu/wiki/index.php/HSV]
HSV 3 dimensional space, but not cubic
cone-like
hue 0 to 360
saturation & intensity real numbers between 0 & 1
for robotics equipment is expensive
SCT = spherical coordinate transform alternative color space being explored
for robotics (often used in astronomical studies)
6.6.3 Region segmentation
Region segmentation identify a region in the image with a particular color
most ubiquitous use of computer vision in robotics
identify all the pixels which are & are not part of the region
used in navigation e.g., travel to regions center (centroid)
Centroid in mathematics the centroid is the point at which the region/volume is equally balance [http://en.wikipedia.org/wiki/Finding_the_centroid]
Binary image representation of image has only 2 values, e.g., red & not-red
Thresholding partitioning of color image into binary image
Foreground the object of interest
Background everything else
Thresholding requires significant contrast between foreground & background
Blob another word for a region of interest
Blob analysis extracting region from image
6.6.4 Color histogramming
Histogram bar chart of data
Bucket a particular range of data values
Color histogram bar chart produced when buckets are specified for color
ranges
Histogram intersection the ratio of matched pixels to total pixels
Constructing & storing a color histogram of an object of interest can be thought
of as imprinting
Intersection can then be considered a measure of the strength of a stimulus
Can be used to construct game-of-tag behavior
6.7 Range from Vision
Big issue in computer vision how to extract range information
Stereopsis depth perception produced by triangulating images from two eyes
Depth perception also induced from optic flow & simple cues, e.g., shadows, texture, & expected size of objects
6.7.1 Stereo camera pairs
Using two cameras to extract range data is known as . .
range from stereo
stereo disparity
binocular vision
stereo
Cameras are known as a stereo pair
Vergance on a point find the same point in each image; turn camera to
center that point; measure relative angle
Two challenges
hard to design & build mechanism to precisely move to verge on the
points
Correspondence problem how to know it is the same point in both
images?
Interest operator algorithm to identify & select interesting or uniquely
valued pixels in an image
Problem pixel value not likely to be precisely identical from 2 angles
Solution acquire list of interesting pixels & find best correspondence between
all of them
Rectified images produced by 2 cameras mounted in place with optic axes
parallel to each other & perpendicular to the mount
baseline space between the axes
disparity difference in images of location of the point
distance is then inversely proportional to the disparity
but this does not solve correspondence problem
Equipolar lines (projections of the equipolar plane) rows of each image
which correspond (capture the same part of space)
Only works if cameras remain in alignment
Camera calibration periodic compensation for inevitable alignment
Changes
Stanford Cart (Hans Moravec) 1st robot to use stereo vision successfully
A major drawback computational expense; can take minutes
6.7.2 Light stripers
Light striping = light stripers = structured light detectors projection of
colored line (stripe), grid, or pattern of dots on the environment
Image was then analyzed to extract information about environment
4.2 Laser Light Striping
Laser light striping is a vision-based technique
of generating a 3-D profile of visual scene. A line
of laser light is projected onto the surface being
profiled while a camera records the resulting image.
The known geometry of the camera and the light
stripe can then be used to triangulate the 3-D
locations of the points on the surface that are
illuminated by the laser.
[http://www.frc.ri.cmu.edu/~ssingh/pubs/fsr01.pdf]
Method was popular in 80s & 90s
Did not transfer well to mobile robots, though Sojourner Mars used it for
obstacle avoidance
6.7.3 Laser ranging
Laser ranging laser beam is emitted
Advantage
almost infinitesimal field of view
can be directed in a scan to cover area & produce image
Ladar (or lidar) laser radar
can generate up to 1 million range pixels per sec
range up to 30 meters
accuracy of a few millimeters
BUT very expensive
produces 2 images intensity & range
range segmentation using trig to convert image to conventional
representation
Problems
errors due to out of range conditions
absorption of light
optical equivalence of specular reflection
6.7.4 Texture
Lightweight vision systems that are simplified by making use of specifics of
environment in which they will operate; see: https://dspace.mit.edu/bitstream/1721.1/16965/1/53448797.pdf
Example Polly, tour guide at MIT & Brown
Focus on texture of carpet, which was more stable than color
6.8 Case Study: Hors dOeuvres, Anyone?
6.9 Summary
Design of perceptual schema or a sensor suite requires careful analysis
Choice must fit:
task
power
processing constraints
& provide complete coverage of all perceptual processing
Other Sources
http://www.kovan.ceng.metu.edu.tr/~emre/literature/Notes_from_Introduction_to_AI_Robotics.html
Further Notes
dead reckoning {from
Wikipedia}
Dead reckoning
(DR) is the process of estimating one's current position based upon a
previously determined position, or
fix, and advancing that position based upon measured velocity, time,
heading, as well as the effect of currents or wind. While this method of
navigation is no longer considered primary in ships, aircraft, automobiles,
rail engines, and construction site engines (tunnels), it is still often used as
a backup in case of failure of the electronic navigation systems.
proprioception {from Wikipedia}
Proprioception (PRO-pree-o-SEP-shun (IPA
pronunciation: [ˈpɹopɹiːoˌsɛpʃən]);
from
Latin proprius, meaning "one's own" and perception) is the
sense of the relative position of neighbouring parts of the body. Unlike the
six
exteroception senses (sight,
taste,
smell,
touch,
hearing, and
balance) by which we perceive the outside world, proprioception is an
interoception sense that provides feedback solely on the status of the
body internally. It is the sense that indicates whether the body is moving with
required effort, as well as where the various parts of the body are located in
relation to each other.
Kinesthesia is another term that is often used interchangeably with proprioception. Some users differentiate the kinesthetic sense from proprioception by excluding the sense of equilibrium or balance from kinesthesia. An inner ear infection, for example, might degrade the sense of balance. This would degrade the proprioceptive sense, but not the kinesthetic sense. The infected person would be able to walk, but only by using the person's sense of sight to maintain balance; the person would be unable to walk with eyes closed.
Kinesthesia is a key component in muscle memory and hand-eye coordination and training can improve this sense (see blind contour drawing). The ability to swing a golf club, or to catch a ball requires a finely-tuned sense of the position of the joints. This sense needs to become automatic through training to enable a person to concentrate on other aspects of performance, such as maintaining motivation or seeing where other people are.
Philosophy of perception {http://nostalgia.wikipedia.org/wiki/Philosophy_of_perception}
First I want you to draw a distinction between two kinds of perception. We can perceive what's going on in our bodies; for example, we can sense where our limbs are, whether we're sitting or standing; we can also sense whether we are hungry, or tired, and so forth. Call that internal perception, or if you want an impressive long word, it's proprioception. We can also perceive the world outside our bodies; using the senses of sight, hearing, touch, smell, and taste, we discover the colors, sounds, textures, and so forth, of the world. Call that sense-perception, or if you want the word corresponding to "proprioception," it is exteroception. So internal perception is the feeling of what's going on in our own bodies, while sense-perception is the perception, using the senses, of the objects and qualities of the world at large.
Philosophy of perception {http://en.wikipedia.org/wiki/Philosophy_of_perception}
We can categorize perception as internal or external.
Internal perception (proprioception) tells us what's going on in our bodies. We can sense where our limbs are, whether we're sitting or standing; we can also sense whether we are hungry, or tired, and so forth.
External or Sensory perception (exteroception), tells us about the world outside our bodies. Using our senses of sight, hearing, touch, smell, and taste, we discover colors, sounds, textures, etc. of the world at large. There is a growing body of knowledge of the mechanics of sensory processes in cognitive psychology.
The philosophy of perception is mainly concerned with exteroception. When philosophers use the word perception they usually mean exteroception, and the word is used in that sense everywhere.