Murphy :: 1-6

Study Material for MidTerm

CIS480

Here are some notes to help you as you study for the MidTerm exam.

Introduction to AI Robotics

Robin R. Murphy

Outline

I. Robotic Paradigms

paradigm – set of assumptions or techniques which characterize an approach to a class of problems

primitives of robotics – sense, plan, act

how paradigms are described

by relationship among primitives of robotics
how sensory data is processed & distributed

The 3 main paradigms:

Hierarchical
Reactive
Hyrid – deliberative/reactive

architecture – principled way of organizing a control system

Dimensions for evaluating suitability of an architecture to an application domain:

Modularity
Niche targetability
Portability
Robustness

1. From Teleoperation to Autonomy

1.1 Overview

1.2 How Can a Machine Be Intelligent?

1.3 What Can Robots Be Used For?

1.3.1 Social implications of robotics

Luddite – person who objects to technology

1.4 A Brief History of Robotics

1.4.1 Industrial manipulators

1.4.2 Space robotics and the AI approach

1.5 Teleoperation

1.5.1 Telepresence

1.5.2 Semi-autonomous control

1.6 The Seven Areas of AI

The 7 areas of AI

Knowledge representation
Understanding natural language
Learning
Planning & problem solving
Inference
Search
Vision

1.7 Summary

2. The Hierarchical Paradigm

2.1 Overview

2.2 Attributes of the Hierarchical Paradigm

Attributes of Hierarchical Paradigm

Sequential
Orderly
Monolithic
World model – a global data structure

Components of Hierarchical Paradigm

a priori representation of environment
sensing information
additional cognitive knowledge

2.2.1 STRIPS

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

2.2.2 More realistic STRIPS example

2.2.3 STRIPS summary

2.3 Closed World Assumption and the Frame Problem

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

2.4 Representative Architectures

2.4.1 Nested Hierarchical Controller

2.4.2 NIST RCS

2.4.3 Evaluation of hierarchical architectures

2.5 Advantages and Disadvantages

Primary advantage – provides ordering of relationship among sense, plan, act

Disadvantages

Sensing/planning algorithms slow

Sensing/acting disconnected

No stimulus/response actions

Dependence on world model creates frame problem

Did not handle uncertainty

sensor noise

actuator errors

action completion failures

2.6 Programming Considerations

2.7 Summary

3. Biological Foundations of the Reactive Paradigm

3.1 Overview

Influential researchers

Hans Moravec – Stanford cart

Michael Arbib – investigate models of animal intelligence

Valentino Braitenberg – Vehicles

3.1.1 Why explore the biological sciences?

Provide existence proofs of intelligence

Give insights into how to organize intelligence

Animals . .

perform sensor fusion

live in the open world

avoid frame problem

3.1.2 Agency and computational theory

Features of agent

self contained

independent

self-aware

3.2 What Are Animal Behaviors?

Ethology – scientific study of animal behaviors

Pioneers

Charles Darwin

George Romanes

Konrad Lorenz

Niko Tinnergen

Oskar Heinroth

Karl von Frisch

3.2.1 Reflexive behaviors

Three types

reflexes – lasts only for duration of stimulus

taxes – oriented with respect to stimulus

fixed action patterns – continue beyond duration of stimulus

3.3 Coordination and Control of Behaviors

How acquire behavior

born with

simple behavior (innate)

sequence of innate behaviors

initialization process (innate with memory)

learn

3.3.1 Innate releasing mechanisms

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

3.4 Perception in Behaviors

3.4.1 Action-perception cycle

3.4.2 Two functions of perception

Perception serves 2 functions

release a behavior, e.g., IRM

guide a behavior – perceive information needed to accomplish behavior

3.4.3 Gibson: Ecological approach

Brooks (or Gibson) – “the world is its own best representation”

affordance – perceivable potentiality for an action

3.4.4 Neisser: Two perceptual systems

2 perceptual systems

direct perception

recogntion

3.5 Schema Theory

Schema – generic template for doing some activity

Consists of

knowledge of how to act and/or perceive

computational process for accomplishing activity

Schema instantiation – creation of specific schema

1.5.1 Behaviors and schema theory

Behavior is comprised of

motor schema – template of the activity

perceptual schema – template for sensing

releaser – trigger for activity

rana computatrix – Arbib’s schema-based computer model of visually guided behaviors in frogs & toads

3.6 Principles and Issues in Transferring Insight to Robots

Programming principles

decompose complex actions into independent behaviors

tightly couple sensing & acting

behaviors are inherently parallel & distributed

use straightforward, Boolean activation mechanisms

use action-oriented perception

filter sensing

consider only what is relevant to the behavior

direct perception (affordances)

reduces computational complexity

permits actions without

memory

inference

interpretation

output from one behavior may

be combined with another’s output

inhibit another

Unresolved issues

resolution of conflicts between concurrent behaviors

when are memory & knowl. Rep. necessary

how to learn/set up new sequences of behaviors

3.7 Summary

4. The Reactive Paradigm

4.1 Overview

Study Reactive Paradigm because

reactive robotic systems still built

form basis of Hybrid 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

Brooks

Arkin

Payton

resolution of conflicts between concurrent behaviors

when are memory & knowl. Rep. necessary

how to learn/set up new sequences of behaviors

4.2 Attributes of Reactive Paradigm

Attributes

all actions accomplished through behaviors

sense-act organization

perception & action tightly coupled

sensing behavior-specific (local to each behavior)

behaviors independent in perception & action

Features

rapid execution

often implemented directly in hardware as circuits

no memory

controlled by what is happening in world

Five main characteristics

1. Situated agent (ecological robotics)

2. Overall behavior is emergent (no external controller of all behaviors)

3. Only local, behavior-specific sensing permitted (ego-centric coordinates)

4. Good software design principles

modularity

component testing

incremental testing

low coupling (high degree of independence)

high cohesion (date & operations of module related only to purpose

of that module)

complex behaviors comprised of simple primitives

5. Animal models often the basis

4.2.1 Characteristics and connotations of reactive behaviors

4.2.2 Advantages of programming by behavior

4.2.3 Representative architectures

4.3 Subsumption Architecture

Rodney Brooks

naturalistic robots

First to

walk

avoid collisions

climb over obstacles

without move-think-move-think pauses

behavior – network of sensing & acting modules

modules are augmented FSM with

registers

timers

other enhancements

4 aspect of subsumption

modules grouped in layers of competence

higher layer can subsume (override) lower one

inhibition – output of subsumed module blocked

suppression – subsuming module substitutes own output as

input of subsumed module

use of internal states (even local ones) avoided

task -> activate spec. layer which activates lower ones

but: subsumption systems not easily taskable

4.3.1 Example

4.3.2 Subsumption 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

new polar plot created with each update of sensors

output from perceptual schemas can be shared with other layers

4.4 Potential Fields Methodology

4.4.1 Visualizing potential fields

Description of 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 which can be combined to build more complex ones

uniform – same force regardless of where robot is

perpendicular – points away from (or toward) an object

attractive – represent a taxis or tropism

repulsive – opposite of attractive

tangential – spin (either cw or ccw) around an object

4.4.2 Magnitude profiles

Magnitude profile – the way that magnitude of vectors in a field change

Problem with constant magnitude – leads to jerky motion on perimeter of field

Magnitude profiles solve this problem

reflexivity – response to stimulus is proportional to strength of stimulus

linear drop off – magnitude drops off as linear function of distance to

object

exponential drop off – drop off is proportional to square of distance

fine tuning behaviors can be done with magnitude profiles

4.4.3 Potential fields and perception

4.4.4 Programming a single potential field

Primitive potential field is represented by single function

Robot computes effect of potential field at every update

has no memory of where it was previously nor where it has moved to

4.4.5 Combination of fields and behaviors

Potential field architecture

requires that all behaviors be implemented as potential fields

combines behaviors by vector summation

Problems of pF method

update rates – rate of update does not match grid since speed of robot is

not uniform over time

holonomicity – pF treat robot as if it can change velocity & direction

simultaneously (not true of real robots)

local minima – areas in space that have magnitude of zero; robot would

be trapped here, not moving

4.4.6 Example using one behavior per sensor

Example illustrates 2 points

direct coupling of sensing to action works

behavioral programming is consistent with good software eng. Practice

Functional cohesion – every statement in a function has something directly to

do with function’s 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

4.4.7 Pfields compared with subsumption

4.4.8 Advantages and disadvantages

Advantages

a continuous representation

easy to visualize space

easier to visualize robot’s 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

Subsumption architecture

popular

behaviors

purely reflexive

may not use memory

within a layer coordinated by FSM

readily implemented in hardware

arranged in layers of competence

lower layers more general abilities

higher layers

coordinate other layers

have more specific goal-directed behaviors

subsume lower layers

Potential fields

also popular

behaviors implemented as potential fields

all active behaviors contribute a vector

vectors are summed

continuous representation

easier to visualize than rule encoding

readily implemented in software

parameterized for flexibility and reuse

formalizes how to combine behaviors

extensible to 3D

re-usable

can implement subsumption layers with peer behaviors

Both

appear largely equivalent in practice

modularity

niche targetability

portability – relative to complexity of changes in task & envt

Neither

particularly robust

no mechanism to notice that degradation has occurred

5. Designing a Reactive Implementation

5.1 Overview

Two deficits in attempts to program more intelligence into reactive robots

designing behaviors more of an art than a science

mystery – how to integrate behaviors into a system, e.g., creating a

sequence of behaviors

Addressing these deficits

object-oriented approach to designing behaviors

two techniques for managing a sequence of behaviors

FSA – finite state automata [= FSM – FS machines]

scripts

5.2 Behaviors As Objects in OOP

OOP

object consists of

data (attributes)

methods (operations)

Recall – schemas contain specific knowledge, local data structures, other

schemas

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 – composed of at least 1 Motor Schema & 1 Perceptual Schema which

act as methods for the Behavior class

Perceptual Schema – has at least one method which takes sensor input &

transforms it into a data structure called a percept

Motor Schema – has at least one method which transforms percept into a form

representing an action

Behavior object is storage location of percept

Note – definition of behavior is recursive

Primitive behavior

composed of only 1 percp. schema & 1 motor schema

monolithic

usually simple mapping stimulus -> response

Abstract behavior

assembled from other behaviors or . .

has multiple percep. or motor schemas

not to be confused with abstract class in OOP

5.2.1 Example: A primitive move-to-goal behavior

move_to_goa(color)

perceptual schema :: extract_goal(goal_color)

color of coke can is the affordance

computes percept

percept :: angle to center & size of region

motor schema :: pfields.attraction(goal_angle, goal_strength)

schemas are independent entities

perceptual schema does not know motor schema exists

behavior puts percept received from perceptual schema where motor schema

can get it

.attraction suffix to pfields means attraction is a method within the object

pfields

The five primitive potential fields can be encapsulated in one class – Pfields –

which any motor schema can use

5.2.2 Example: An abstract follow-corridor behavior

5.2.3 Where do releasers go in OOP?

Within OOP what object or construct contains releaser?

releaser is itself a perceptual schema

can execute independently

not bound to a motor schema

How is it attached to the behavior?

two approaches are given

5.3 Steps in Designing a Reactive Behavioral System

Specification & analysis: ecological niche

describe the task

describe the robot

describe the environment

Design

describe how the robot should act within environment

Implementation & unit testing

implement & refine each behavior

test each behavior independently

System testing

test behaviors together

5.4 Case Study: Unmanned Ground Robotics Competition

Describe the environment

key factor in determining the situatedness of the robot

identify the perceptual opportunities for the behaviors

Describe how robot should act within environment

behavior table – often useful to construct one

Refine each behavior

consider both

normal expected range

when a behavior will fail (shoes & dandelions)

Test each behavior independently

simulators often model only mechanics of robot, not perceptual abilities

to verify perceptual schema – try it in real world

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

state diagram

transition table

Formal definition :: M = (K, S, d, s, F)

K – finite set of states (represent discrete states of robot)

each q ∈K – listing of behaviors that should be active

S - input alphabet – finite set of inputs

set of

behavioral releasers

stimuli

affordances

recognized by the robot

d - finite transition function

s – the start state (initial state of robot)

F – finite set of final states (indicate robot has completed its task)

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.2 A Pick Up the Trash FSA

5.5.3 Implementation examples

5.5.4 Abstract behaviors

Problems

need to adapt to different situations

exceptions – occur when robot fails in task

need to be recognized

need alternate steps

A possible solution – templates or abstract behaviors

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

5.6 Summary

6. Common Sensing Techniques for Reactive Robots

6.1 Overview

Primary reactive concepts

perception has two roles

release a behavior

guide actions of behavior

all sensing is behavior-specific

behaviors tend to be stimulus-response

recognition is not compatible with reactivity

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 – rely on environment to provide medium (e.g., camera requires

light provided by environment)

active – puts energy into environment, e.g.,

sonar

X-ray

camera with flash

Active sensing – dynamically position sensor to improve sensory data

Sensors which measure same energy & process it in similar ways form

sensor modality, which refers to the raw input to the sensor

6.1.1 Logical sensors

Logical sensor – unit of sensing or module that supplies a particular percept

Consists of

signal processing from physical sensor

software processing to extract percept

Is the functional building block for perception

Contains all available alternative means for obtaining a percept

Logically equivalent – logical sensors that return the same percept data

Structure, though perhaps not equivalent in performance or update rate

6.2 Behavioral Sensor Fusion

Behavioral sensor fusion – any process that combines information from

multiple sensors into single percept

How sensors can be combined

redundant – two or more sensors return same percept (competing)

complementary – disjoint types of info re percept

coordinated – sequence of sensor directed toward a task/goal

Types of sensor fusion

action-oriented sensor fusion – percepts fused into one which is supplied

to a beahvior

sensor fission – percept sent to separate behaviors whose action is

combined

sensor fashion – percepts sent to selector mechanism which selects

which sensor’s percept is supplied to the behavior; choice changes

with changing circumstances

6.3 Designing a Sensor Suite

Sensor suite – the set of sensors used by the robot

Designing – begins with assessment of type of information needed

Categories of sensing

Proprioception – measurements of movements relative to robot’s internal

frame of reference

Exteroception – measurements of layout of environment & its objects

relative to robot’s frame of reference

Exproprioception – measurements of robot’s body or parts relative to the

layout of the environment

6.3.1 Attributes of a sensor

Attributes to consider for any 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

6.3.2 Attributes of a sensor suite

Attributes to consider for entire sensor suite

Simplicity – complexity requires maintenance & more modes of failure

Modularity – presence or absence of one sensor does not affect others

Redundancy – to overcome errors/failures

physical redundancy – multiple instances of identical sensors

logical redundancy – different modalities produce same percept

Fault tolerance – surviving a failure

Error/failure detection – robot knows e/f has occurred

6.4 Proprioceptive Sensors

Shaft encoder – measures number of turns a motor has made

Proprioception is often an estimate

6.4.1 Inertial navigation system (INS)

INS – measure movements electronically through miniature accelerometers

expensive

large

small ones less accurate

hard bump or sudden turn can introduce errors

6.4.2 GPS

Global positioning system – receiver triangulates itself relative to 4 GPS

satellites

Navstar constellation – USAF

GLONOSS – Russian Federation Ministry of Defense

Differential GPS – improve accuracy by using 2 recievers, 1 of which is

stationary

GPS does not work indoors in most buildings

Skyscrapers act as urban canyons & interfere with reception

6.5 Proximity Sensors

Most proximity sensors are active