Course Search, Navigate, and Actuate
"Zoeken, Sturen en Bewegen"
This is the information of year 2012.
The site of the previous 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
- alpha-beta 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 self-parking 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 (coordinate-free)
- 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
- Denavit-Hartenberg 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 23
Download Lecturnity Player to listen to lecture,
synchronized with the sheets.
Search
date
|
time
|
type
|
subject
|
location
|
lecturer/assistant
|
Monday 4/6 |
9.00-9.15 |
L0 |
Course Overview Lecture pdf, recording lpd |
G0.18 |
Arnoud Visser |
Monday 4/6 |
9.15-11.00 |
SCR1 |
Searching through Game Trees - minimax and alpha-beta
Lecture pdf, recording minimax lpd, recording alpha-beta lpd. |
G0.18 |
Arnoud Visser, Elise Koster |
fig22_3.txt |
Monday 4/6 |
11:00-17:00 |
SCR2 |
Searching through Game Trees - Advice Language
Lecture ppt, recording Advice Language for Tic-Tac-Toe lpd |
(follow_strategy.pl),
(advice.pl)
G0.12, G0.23, G0.25 |
Arnoud Visser, Camiel Verschoor |
fig22_5.txt |
Tuesday 5/6 |
9.00-11.00 |
L1 |
Qualitative Navigation Lecture (pdf 1.1 Mb), recording (lpd 32 Mb) Distinctive Place Movie (88 Mb) Visual Homing Movie (15 Mb) |
G2.10 |
Arnoud Visser |
Tuesday 5/6 |
11.00-13.00 |
P1 |
Task 1: Endgames |
G0.12, G0.23, G0.25 |
Julian Kooij |
Tuesday 5/6 |
13.00-17.00 |
ZS |
Task 1: Endgames |
G0.12, G0.23, G0.25 |
No assistance |
Wednesday 6/6 |
11.00-13.00 |
ZS |
Task 1: Endgames |
G0.12, G0.23, G0.25 |
no assistance, Walibi Day |
Thursday 7/6 |
9.00-11.00 |
L2 |
Quantative Navigation Lecture (pdf 194 Kb), recording lpd, Voronoi graph movies. |
P2.10 |
Arnoud Visser |
Thursday 7/6 |
11.00-13.00 |
P2 |
Task 1: Endgames |
G0.12, G0.23, G0.25 |
Julian Kooij |
Thursday 7/6 |
13.00-17.00 |
ZS |
Task 1: Endgames |
G0.12, G0.23, G0.25 |
No assistance |
Friday 8/6 |
11.00-13.00 |
ZS |
Task 1: Endgames |
G0.12, G0.23, G0.25 |
no assistance, 'Active Leden Weekend' |
Week 24
Navigate
date
|
time
|
type
|
subject
|
location
|
lecturer/assistant
|
Monday 11/6 |
9.00-11.00 |
L3 |
Path Planning algorithms |
G2.10 |
Leo Dorst |
|
Monday 11/6 |
11.00-17:00 |
Pres |
demonstration student solutions
| G0.23, G0.25 |
Julian Kooij,
Arnoud Visser |
Monday 11/6 |
11.00-13:00 |
P3 |
Task 2: Path planning module |
G0.12 |
Toto van Inge
|
Tuesday 12/6 |
9.00-11.00 |
L4 |
rotations en homogeneous coordinates |
C0.110 |
Leo Dorst |
Tuesday 12/6 |
11.00-13:00 |
P4 |
Task 2: Path planning module |
G0.12, G0.23, G0.25 |
Toto van Inge
|
Tuesday 12/6 |
13.00-17.00 |
ZS |
Task 2: Path planning module |
G0.12, G0.23, G0.25 |
no assistance |
Wednesday 13/6 |
9.00-11.00 |
L5 |
kinematics: Denavit Hartenberg |
G2.10 |
Leo Dorst |
Wednesday 13/6 |
11.00-13:00 |
P5 |
Task 2: Path planning module |
G0.12, G0.23, G0.25 |
Toto van Inge
|
Wednesday 13/6 |
13.00-17.00 |
ZS |
Task 2: Path planning module |
G0.12, G0.23, G0.25 |
no assistance |
Thursday 14/6 |
9.00-11.00 |
L6 |
inverse kinematics |
G2.10 |
Leo Dorst |
Thursday 13/6 |
11.00-13:00 |
P6 |
Task 2: Path planning module |
G0.12, G0.23, G0.25 |
Toto van Inge
|
Thursday 14/6 |
13.00-17.00 |
ZS |
Task 2: Path planning module |
G0.12, G0.23, G0.25 |
no assistance |
Friday 15/6 |
9.00-11.00 |
|
No Lecture
| |
|
Friday 15/6 |
11.00-13:00 |
P7 |
Task 2: Path planning module |
G0.12, G0.23, G0.25 |
Toto van Inge
|
Friday 15/6 |
13.00-17.00 |
ZS |
Task 2: Path planning module |
G0.12, G0.23, G0.25 |
no assistance |
Week 25
Actuate
Week 26
Go, where no one has gone before.
date
|
time
|
type
|
subject
|
location
|
lecturer/assistant
|
Monday 20/6 |
9.00-12.00 |
Experiment1 |
Kick-Off |
G0.18 |
Arnoud Visser |
Monday 20/6 |
12.00-17.00 |
ZS |
|
G0.18 |
no assistance |
Tuesday 21/6 |
9.00-17.00 |
ZS |
|
G0.18 |
no assistance |
Wednesday 22/6 |
9.00-12.00 |
Experiment2 |
Mid-Term |
G0.18 |
Arnoud Visser |
Wednesday 23/6 |
12.00-17.00 |
ZS |
|
G0.18 |
no assistance |
Thursday 23/6 |
9.00-17.00 |
ZS |
|
G0.18 |
no assistance |
Friday 24/6 |
9:00-17.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:
- Path-planning for a Hemisson-robot
- Talking mouth for a Aibo-robot
- Maze navigation with a Nao-robot
- Looking to a talking person with a Nao-robot.
- 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.7 .
Literature
For the implementation in prolog we will look at chapter 24 of
Prolog Programming for Artificial Intelligence by
Ivan Bratko. The companion website of the 4th edition is not yet available, the companion website of the 3th edition contains several student resources.
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 / Autonomous Mobile Robots. 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 VIA-site).
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 July 3, 2012
This web-page and the list of participants to this course is maintained by
Arnoud Visser
(arnoud@science.uva.nl)
Faculty
of Science
University of Amsterdam