Course Search, Navigate, and Actuate
"Zoeken, Sturen en Bewegen"
This is the information of year 2004.
 The information of previous year can be found here.
 The information of the current year can be found here.
Description
The official description of course baiZSB6 can be found (in Dutch)
here. The organisation part is already outdated. Also a Blackboard portal to this information is available.
Contents
 Search Algorithms
Game playing is an example of type of problems that can easily
decomposed in subproblems. For interesting games, like chess,
the tree of subproblems grows to fast to be searched exhaustively,
so other approaches are necessary. To solve the game we have
to find a solution tree regardless of the opponent's replies.
The natural way to represent such a two person, perfect information
game, is with AND/OR graphs. Our positions are are represented
as ORnodes, because we have only to make one winning move.
Their positions are represented as ANDnodes, because if their
is winning move for the opponent, we have to assume that they
will find it.
 Problem decomposition
 AND/OR graphs
 MiniMax principle
 alphabeta algorithm
 Path planning
You have had planning algorithms such as A*
that work on graphs. So let's try to reformulate the path planning
problem as a graph problem. These graphs are somewhat special, it
is convenient to see them as discretized spaces because this leads to
better implementations. So then we need the notion of configuration
space to explain the graph's properties.
 A* revisited
 Mapping path planning as graph search
 Task space and discretized configuration space
 Kinematics > connectivity
 Criteria > metric
 Obstacles > forbidden nodes
 Examples: robot arm and selfparking car
 Other approaches of mapping path planning into graphs
 Trajectory planning
If you have setpoints, how to make it into a controllable path.
 Rigid body motion

physical rigid bodies as idealization
 physical space as vector space
 representing motions using linear algebra (coordinatefree)
 isometries
 proof of decomposition theorem: rigid body motion = rotatio
n followed by translation
 coordinates: vector spaces in the computer
 rotation matrices: how to design them
 reference angles:
Euler angles
 homogeneous coordinates
 Kinematics of linked mechanisms
 DenavitHartenberg notation
 Forward kinematics
 Inverse kinematics (briefly)
 Redundancy and degeneracy (briefly)
 Differential kinematics
Schedule
Week 23
date

time

type

subject

location

lecturer/assistant

Monday 31/5 
Whit Monday 
Tuesday 1/6 
10.0010.15 
L1 
Course Overview Lecture (614 Kb) 
Studio Classroom  Amstel Instituut, Kruislaan 404 
Arnoud Visser 
Tuesday 1/6 
10.1512.00 
L1 
Problem Decomposition and AND/OR Graphs 
Studio Classroom  Amstel Instituut, Kruislaan 404 
Maarten van Someren 
Tuesday 1/6 
12.3014.30 
W1 
decomposition problems 
Studio Classroom  Amstel Instituut, Kruislaan 404 
Maarten van Someren 
Tuesday 1/6 
15.0017.00 
L2 
the minimax principle and the alphabeta algorithm 
Studio Classroom  Amstel Instituut, Kruislaan 404 
Maarten van Someren 
Wednesday 2/6 
10.0012.30 
P1 
Checkmate 
P.126 
Matthijs Spaan, Coen Pieterse 
Wednesday 2/6 
13.0015.00 
L4 
Qualitative Navigation Lecture (461 Kb) Movie (88 MB) 
P.017 
Arnoud Visser 
Wednesday 2/6 
15.3016.30 
W2 
introduction Dataconversion 
Studio Classroom  J.302 Valckenierstraat 65 
Matthijs Spaan, Coen Pieterse 
Thursday 3/6 
10.0012.30 
P1 
Checkmate 
P.126 
Matthijs Spaan, Coen Pieterse 
Thursday 3/6 
13.0015.00 
L5 
Quantative Navigation Lecture (126 Kb) 
P.017 
Arnoud Visser 
Friday 4/6 
10.0012.30 
P2 
A* in Java 
P.126 
Matthijs Spaan, Coen Pieterse 
Week 24
date

time

type

subject

location

lecturer/assistant

Monday 7/6 
10.0012.30 
P3 
high path 
P.126 
Matthijs Spaan, Coen Pieterse 
Monday 7/6 
13.0015.00 
selfstudy 
path planning: Cspace 


Tuesday 8/6 
10.0012.30 
P3 
high path 
P.126 
Matthijs Spaan, Coen Pieterse 
Tuesday 8/6 
13.0015.00 
selfstudy 
path planning: structure 


Wednesday 9/6 
10.0012.30 
P4 
path to garbage 
P.126 
Matthijs Spaan, Coen Pieterse 
Wednesday 9/6 
13.0015.00 
L8 
path planning: algorithms 
P.017 
Leo Dorst 
Thursday 10/6 
10.0012.30 
P5 
low path 
P.126 
Matthijs Spaan, Coen Pieterse 
Thursday 10/6 
13.0015.00 
L9 
rotations en homogeneous coördinates 
P.017 
Leo Dorst 
Friday 11/6 
'open dag op locatie' 
Week 25
Monday 14/6 
10.0012.30 
P6 
kinematics 
P.126 
Matthijs Spaan, Coen Pieterse 
Monday 14/6 
13.0015.00 
L11 
kinematics: Denavit Hartenberg 
P.017 
Leo Dorst 
Tuesday 15/6 
10.0012.30 
P6 
kinematics 
P.126 
Matthijs Spaan, Coen Pieterse 
Tuesday 15/6 
13.0015.00 
L12 
inverse kinematics 
P.017 
Leo Dorst 
Wednesday 16/6 
10.0012.30 
P7 
inverse kinematics 
P.126 
Matthijs Spaan, Coen Pieterse 
Friday 18/6 
10.0016.00 
P8 
integration and demonstration 
Robotlab  F1.21, Kruislaan 403 
Matthijs Spaan 
Week 26
Go, where no one has gone before.
his time it is not the result that counts, but your summery of your survey.
Document your progress, experiments and decisions in a LabBook.
Monday 21/6 
10.0012.00 
Experiment1 
KickOff 
P.126 
Arnoud Visser 
Wednesday 24/6 
10.0012.00 
Experiment2 
MidTerm 
P.126 
Arnoud Visser 
Friday 26/6 
10.0013.30 
Experiment3 
Demonstration and Documentation 
Robotlab  F1.21, Kruislaan 403 
Arnoud Visser 
Friday 26/6 
14.0017.00 
Experiment4 
Grade & Drinks 
Euclides, Ground Floor 
Arnoud Visser 
With a working system, and the acquired knowledge, you can explore
new possibilities. Here are some suggestions:
 Extend the checkmate problem to more complex situations
 Play on a tilted board
 Play on a NewChess board
 Java implementation of the alphabeta algorithm
 Use an Aibo as webcam
 Let the Aibo move one piece
 Create a 8x8 maze for the Aibo
 Create a maze for a plotterrobot
 Create 2D Gameinterface with GameMaker.
It is recommanded to work in groups of three students.
You will be evaluated on your LabBook at the end of
the week.
For the list of Labbooks of the 2004 students, see Experiment2004
Results
The results can be found here.
Evaluation
The course was overall evaluated by the participants with a 7.4.
Literature
We start with chapter 13 and 22 of
Prolog Programming for Artificial Intelligence by
Ivan Bratko.
We continue with the second part of
Introduction to AI Robotics by
Robin Murphy: Navigation.
The University of Tennessee has a course that is also based on this textbook.
Further use lecture notes and a lab manual.
Inheritance
In the old days, when Bachelors were not schooled at Dutch Universities,
a different course was given with another focus.
Still, much can be learned from the course 'Robotica'.
Last updated 28 July 2004
This webpage and the list of participants to this course is maintained by
Arnoud Visser
(arnoud@science.uva.nl)
Faculty
of Science
University of Amsterdam