Transcript last

Topics since last test



Graphics
Software design
 Recursion
 Arrays
 Copyright issues
Computer systems
 Hardware
 Architecture
 Operating Systems
 Security
CPS 001


Computer Science Theory
 Performance of
algorithms
 Complexity
 Computability
Debate Topics
1
The exam





Tuesday, May 2, 2pm-5pm in B101 LSRC
Open book/open note
~40% multiple choice/short answer
Cumulative
By Friday, April 28 at 5pm:
 All grades up (except final project)
 All solutions out
 Grade problems:
Submit throught Eclipse assignment name issues

Final grades up Friday, May 5
CPS 001
2
Help Sessions
1.
2.
Sun 3-5pm
M 5:30-6:30
In D106 LSRC (look for email reminder)
CPS 001
3
Essential concepts
There is beauty at all levels of sophistication and all
levels of abstraction.
- David A. Blackwell
If life were really fair, algebra would actually come
in handy
- Amstel Light commercial
CPS 001
4
On programming and deadlines
Observe that for the programmer, as the chef, the urgency of
the patron may govern the scheduled completion of task, but
it cannot govern the actual completion. An omelet, promised
in two minutes, may appear to be progressing nicely. But
when it has not set in two minutes, the customer has two
choices -- wait or eat it raw. Software customers have the same
choices..
- Fred Brooks
We don’t have time to stop for gas -- we’re already late.
- Old software project planning proverb via Mike Cleron
I love deadlines. I like the whooshing sound they make as
they fly by.
- Douglas Adams
CPS 001
5
Why is programming fun?
What delights may its practitioner expect as a reward?
First is the sheer joy of making things
Second is the pleasure of making things that are useful
Third is the fascination of fashioning complex puzzlelike objects of interlocking moving parts
Fourth is the joy of always learning
Finally, there is the delight of working in such a
tractable medium. The programmer, like the poet,
works only slightly removed from pure thought-stuff.
Fred Brooks
CPS 001
6
On education
The college you attend does not determine the scope and
possibility of your life’s achievements. It will have some
influence, no doubt. What is more important is the
encouragement that we, as parents and friends, offer these
prospective students as they explore their own educational
trail. In the end, the experiences they encounter and the depth
of character they build along the way will mean far more than
the name of the institution on their diploma.
- John Hennesy
Education is not filling a bucket but lighting a fire.
- William Yeats
CPS 001
7
On education
An education isn’t how much you have committed to memory, or
even how much you know. It’s being able to differentiate between
what you know and what you don’t.
- Anatole France
The best way to have a good idea is to have lots of ideas.
- Linus Pauling
If there is no struggle, there is no progress
- Frederick Douglass
The ability to quote is a serviceable substitute for wit.
- W. Somerset Maugham
CPS 001
8
Who are these people? Why are
they important?
CPS 001
9
Who are these people? Why are
they important?
CPS 001
10
Who are these people? Why are
they important?
CPS 001
11
Laws governing computer science



Moore’s Law (1965)
 The number of transistors per area on a chip double every
18 months
 Density of transistors => more functionality and speed
How about multiple computers?
Amdahl’s Law (1967)
 Given: fraction (s) of work to be done is serial (i.e. isn’t
parallelizable)
 Maximum speedup with infinite number of processors is
1/s
CPS 001
12
What are computers for?



Simulation
Communication among people
 Storage = communication across time
Control
 Get physical
 Get real (time)
 Get mobile
CPS 001
13
Application



Simulation
 Models of the real world (e.g. planets, cities,
molecules)
Communication among people
 Information at your fingertips
 Telepresence
 Home
Control
 Robots
 Software agents
CPS 001
14
What’s next




CompSci 4
 Robots
 Video games
 Java
CompSci 6
 Assumes knowledge of loops & arrays
Seminars
 Animation and virtual worlds
 History of Communication
Interdisciplinary minor
 Computational Biology & informatics
 Computational Economics
CPS 001
15
CPS 001
16
NYTimes in 1984
CPS 001
17
CPS 001
18
CPS 001
19
What do I do? Robotics & AI

Making systems that act rationally

Interesting problems
 Robocup
 Autonomous vehicle control
CPS 001
20
Robocup

The Goal: By the year 2050, develop a team of fully
autonomous humanoid robots that can win against the
human world soccer champion team
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
CPS 001
21
Robocup Rescue


Goal: When disaster happens, minimize risk to search and
rescue personnel, while increasing victim survival rates, by
fielding collaborative teams of robots that can:
 Autonomously negotiate compromised and collapse
structures
 Find victims and ascertain their conditions
 Produce practical maps of their locations
 Identify hazards
 Deploy sensors (acoustic, thermal, hazmat, seismic,...)
 Provide structural shoring
... allowing human rescuers to quickly locate and extract
victims
CPS 001
22
Outreach



How can we use robots to inspire middle school
students?
What about the Digital Divide?
RoboCupJunior: International, national, and
regional competitions for elementary, middle, and
high school students
CPS 001
23
Autonomous Vehicle Control:
The World
•
•
Noisy, unpredictable and hostile
CPS 001
Delayed
feedback from actions
•

Partially Observable
Significant challenge for AI
24
Autonomous Vehicle Control:
Approaches


Vehicle control
 Significant progress on low-level sensing and control
 [Dickmans and Zapp, 1987; Godbole and Lygeros, 1993;
Pomerleau, 1993; Malik et al., 1997]
High-level reasoning
 SAPIENT system at CMU
 RL methods
 The Bayesian Automated Taxi Project
• Goal: Develop and test control architecture for learning control
of autonomous vehicles
• Domain: Simulator
– Much safer!
CPS 001
25
Autonomous Vehicle Control:
Learning to Drive

No single optimal trajectory or path


Developed an explicit policy representation for control which
performed robustly in a number of driving scenarios


Somewhat fragile and not easily adaptable
Reinforcement learning (RL)


Not easily amenable to supervised learning or regulatory control methods
Successively improves and adapts control strategies through trial-and-error
interactions with a dynamic environment
RL techniques have shown some promise in solving complex control
problems


CPS 001
TD-Gammon [Tesauro, 1992], Inverted helicopter control [Ng, 2004],
Dialogue management, Intelligent tutoring systems
Need to scale and extend for continuous control domains
26
Reinforcement Learning in MDPs

Markov Decision Problems / Optimal control
 Theoretical framework for controllers to maximize some external
performance criteria
Agent
State
st
Reward
rt
Action
ut
Environment

Definitions:



CPS 001

State - A particular situation in the world as viewed by
agent
Policy What to do in every state
Model What follows what
Reward What is good
27
What is SLAM?

Simultaneous Localization and Mapping

Localization
 Finding one’s place within a map
 Typically assumes a map
 Uses only built-in sensors (no GPS!)
 (Relatively) easy with 100% accurate map
Mapping
 Building a representation of the world
 (Relatively) easy with 100% accurate localization

CPS 001
28
Example Applications

Planetary exploration
Search and Rescue
Hostage/terrorist situations
De-mining (land/sea)
Blueprint correction

Need robot’s eye view of the world




CPS 001
29
Example Robot
CPS 001
Markov the robot, generously donated by SAIC
30
Example Map
CPS 001
31
Why is SLAM hard: Odometry
Actual
trajectory
Odometry
CPS 001
32
Why is SLAM Hard: Ambiguity
End
Start
DARPA Grand Challenge



Follow a route
Avoid obstacles
Win $2 million!
CPS 001
34