Course Search, Navigate, and Actuate
"Zoeken, Sturen en Bewegen"
This is the information of year 2005
The site of the previous year 2004 can be found here.
Description
The official description of course baiZSB6 can be found (in Dutch)
here. 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.- 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 = 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
- Denavit-Hartenberg notation
- Forward kinematics
- Inverse kinematics (briefly)
- Redundancy and degeneracy (briefly)
- Differential kinematics
Schedule
Week 23
| date | time | type | subject | location | lecturer/assistant |
| Monday 6/6 | 10.00-10.15 | L1 | Course Overview Lecture(ppt 614 Kb)(pdf 182 Kb) |
P1.24 | Arnoud Visser |
| Monday 6/6 | 10.15-12.00 | L2 | Searching through Game Trees - minimax and alpha-beta(ppt 794 Kb)(pdf 226 Kb) | P1.24 | Arnoud Visser |
| Monday 6/6 | 12.30-14.30 | L3 | Searching through Game Trees - Advice Language (794 Kb) | P1.24 | Arnoud Visser |
| Tuesday 7/6 | 10.00-12.30 | P1 | Endgames | P.124 | Jasper Uijlings |
| Tuesday 7/6 | 13.00-15.00 | L4 | Qualitative Navigation Lecture (ppt 427 Kb)(pdf 408 Kb) Movie (88 MB) |
P.227 | Arnoud Visser |
| Tuesday 7/6 | 15.30-17.00 | P1 | Endgames | P1.24 | self-study |
| Wednesday 8/6 | 10.00-12.30 | P2 | Endgames | P.124 | Jasper Uijlings |
| Wednesday 8/6 | 13.00-15.00 | L5 | Quantative Navigation Lecture (126 Kb) |
E.020 | Arnoud Visser |
| Wednesday 8/6 | 15.30-17.00 | P2 | Endgames | P1.24 | self-study |
| Thursday 9/6 | 10.00-12.30 | P3 | Endgames | P.124 | Jasper Uijlings |
| Thursday 9/6 | 13.00-15.00 | path planning: Cspace | self-study | ||
| Thursday 9/6 | 15.30-17.00 | P3 | Endgames | P1.24 | self-study |
| Friday 10/6 | 'Voorlichting op Locatie' | path planning: structure | self-study | ||
Week 24
| date | time | type | subject | location | lecturer/assistant | ||
| Monday 13/6 | 10.00-12.30 | P4 | high path | P.124 | Olaf Booij | ||
| Monday 13/6 | 13.00-15.00 | L8 | path planning: algorithms | P.227 | Leo Dorst | Monday 13/6 | 15.30-17.00 | P4 | high path | P.124 | self-study |
| Tuesday 14/6 | 10.00-12.30 | P5 | high path | P.124 | Olaf Booij | ||
| Tuesday 14/6 | 13.00-15.00 | L9 | rotations en homogeneous coördinates | P.227 | Leo Dorst | ||
| Tuesday 14/6 | 15.30-17.00 | P5 | high path | P.124 | self-study | ||
| Wednesday 15/6 | 10.00-12.30 | P6 | path to garbage | P.124 | Olaf Booij | ||
| Wednesday 15/6 | 13.00-15.00 | L11 | kinematics: Denavit Hartenberg | P.227 | Leo Dorst | ||
| Wednesday 15/6 | 15.30-17.00 | P6 | path to garbage | P.124 | self-study | ||
| Thursday 16/6 | 10.00-12.30 | P7 | low path | P.124 | Olaf Booij | ||
| Thursday 16/6 | 13.00-15.00 | L12 | inverse kinematics | P.227 | Leo Dorst | ||
| Thursday 16/6 | 15.30-17.00 | P7 | low path | P.124 | self-study | ||
| Friday 17/6 | 10.00-12.30 | P6 | low path | P.124 | Olaf Booij | ||
| Friday 17/6 | 10.30-17.00 | P7 | low path | P.124 | self-study |
Week 25
| Monday 20/6 | 10.00-12.30 | P7 | kinematics | P.124 | Olaf Booij |
| Wednesday 22/6 | 10.00-12.30 | P8 | inverse kinematics | P.124 | Olaf Booij |
| Friday 24/6 | 10.00-16.00 | P9 | integration and demonstration | P.124 | Olaf Booij |
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 27/6 | 10.00-12.00 | Experiment1 | Kick-Off | P.124 | Arnoud Visser | Wednesday 29/6 | 10.00-12.00 | Experiment2 | Mid-Term | P.124 | Arnoud Visser |
| Friday 1/7 | 9.50-13.20 | Experiment3 | Demonstration and Documentation | P.124 | schedule |
| Friday 1/7 | 13.30-15.10 | Experiment4 | 3th year project presentations | Parallel sessions, rooms C.210 and A-B | Bert Bredeweg |
| Friday 1/7 | 15.30-17.10 | Experiment5 | 3th year project presentations | Plenair session, room A-B | Bert Bredeweg |
| Friday 1/7 | from 17.00 | Experiment6 | Grade & Drinks | Hall from building A | Arnoud Visser |
With a working system, and the acquired knowledge, you can explore new possibilities. Here are the current selections:
- Reasoning and actuation in a blockworld.
Dolf Klomp and Kaspar de Geus. - Create a maze generator for the pathplanning module
Dennis Roof and Gijs Pannebakker. - Play a game of Jenga
Kris Bende and Jeroen Kools. - Detect a move with a webcam
Hylke Buisman and Mark Beumer. - Solve Teeko or 'molenspel' with alphabeta algorithm in Java
Rik Tobi, Aksel Ethembabaoglu and Erik van den Hooven. - Create a maze for a Heminson-robot
Anne Schuth and Tjerk Kostelijk. - Make a plotter of the UMI-RTX robot
Folkert Huizinga and Bram Stoeller. - Sudoko
Niels Out and Andreas van Cranenburgh - Solve tic-tac-toe in Advice Language / Dephi
Bruno Jakic.
- Play on a tilted board
- Play on a NewChess board
- Extend the checkmate problem to more complex situations
- Create 2D Game-interface with
GameMaker. - Create a 8x8 maze for the Aibo
You will be evaluated on your LabBook at the end of the week.
Evaluation
The course was overall evaluated by the participants with a 8.0.
Literature
We start with chapter 5 (Game Playing, 1th edition) which is equivalent with chapter 6 (Adversarial Search, 2nd edition) from .
Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig.
Part II of the book is equivalent with the theory behind the previous course Search Techniques. Part III and IV are explored in the proceeding course Symbolic Robotics. Some theory in Minsky and our syllabus can also be found in chapter 25 'Robotics'.
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.
We continue with the second part of
Introduction to AI Robotics by
Robin Murphy: Navigation.
Part I book was explored in the previous course Reactive Behaviours.
The University of Tennessee has a course that is also based on this textbook.
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 26 July 2005
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