Course Search, Navigate, and Actuate
"Zoeken, Sturen en Bewegen"
This is the information of year 2011.
The site of the previous year
can be found here.
The site of the next year can be found here.
The experiments of the last week are listed on a separate page.
Description
The official description of course baiZSB6 can be found (in Dutch)
here.
Also a Blackboard portal to this information is available. Blackboard is mainly used for email and grading.
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.
 MiniMax principle
 alphabeta algorithm
 increasing the effectiveness with advice rules
 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 = rotation 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
This schedule has some correspondance with the official schedule, but in case of doubt use this page as reference.
Week 22
Download Lecturnity Player to listen to lecture,
synchronized with the sheets.
Search
(follow_strategy.pl),
(advice.pl)
Week 23
Navigate
Week 24
Actuate
Week 25
Go, where no one has gone before.
date

time

type

subject

location

lecturer/assistant

Monday 20/6 
9.0012.00 
Experiment1 
KickOff 
G0.18 
Arnoud Visser 
Monday 20/6 
12.0017.00 
ZS 

G0.18 
no assistance 
Tuesday 21/6 
9.0017.00 
ZS 

G0.18 
no assistance 
Wednesday 22/6 
9.0012.00 
Experiment2 
MidTerm 
G0.18 
Arnoud Visser 
Wednesday 23/6 
12.0017.00 
ZS 

G0.18 
no assistance 
Thursday 23/6 
9.0017.00 
ZS 

G0.18 
no assistance 
Friday 24/6 
9:0017.00 
Experiment3 
Demonstration and Documentation 
G0.18 
Arnoud Visser 

Friday 24/6 
from 17.00 
Experiment4 
Barbecue 
near cantine 
VIA 
It is not the result that counts, but your summery of your survey.
Document your progress, experiments and decisions in a LabBook.
With a working system, and the acquired knowledge, you can explore
new possibilities.
Here are the surveys of the previous years:
Here are some suggestions:
 Pathplanning for a Hemissonrobot
 Talking mouth for a Aiborobot
 Maze navigation with a Naorobot
 Looking to a talking person with a Naorobot.
 Extend the checkmate problem to more complex situations
 Refine the visualisation of the Virtual robot.
 Creating a gamepad interface for a virtual Aibo (Visual Basic)
 WiiBot RTX UMI
 Solve chess endgame with Monte Carlo tree search (MCTS)
It is recommanded to work in groups of three students.
You will be evaluated on your LabBook at the end of
the week.
Evaluation
This year the course was overall evaluated by the participants with a 7.5 .
Literature
For the implementation in prolog we will look at chapter 22 of
Prolog Programming for Artificial Intelligence by
Ivan Bratko.
This book was explored until chapter 13 in the previous course Logic Programming and Search Techniques.
A short introduction will be given based on the second part of
Introduction to AI Robotics by
Robin Murphy: Navigation.
Part I book was in the previous years explored in the course Reactive Behaviours. Now this course is replaced the more advanced course Probabibilistic Robotics. Murphy's book is not longer required, and should not be bought. The two chapters are available electronically (Chapter 9 and Chapter 10).
Further we use the syllabus 'An Introduction to Robotics' by Leo Dorst and a
lab manual.
The syllabus available from the Dikatenverkoop (check the
opening times at the VIAsite).
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 May 31, 2012
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