Course Search, Navigate, and Actuate
"Zoeken, Sturen en Bewegen"
This is the information of year 2007
The site of the previous year 2006 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 = 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. And forget in the official schedule anything related to Prof. Dr. J.J. Boon :-).
Week 23
| date | time | type | subject | location | lecturer/assistant |
| Monday 4/6 | 10.00-10.15 | SCR1 | Course Overview Lecture(pdf 454 Kb) |
P1.26 | Arnoud Visser |
| Monday 4/6 | 10.15-12.00 | SCR2 | Searching through Game Trees - minimax and alpha-beta(pdf 355 Kb) | P1.26 | Arnoud Visser |
| Monday 4/6 | 13.00-14.30 | SCR3 | Searching through Game Trees - Advice Language (pdf 226 Kb) (follow_strategy.pl), (advice.pl) |
P1.26 | Arnoud Visser |
| Tuesday 5/6 | 10.00-12.30 | P1 | Task 1: Endgames | P1.26 | Martijn Liem |
| Tuesday 5/6 | 13.00-15.00 | L1 | Qualitative Navigation Lecture (pdf 1.1 Mb) Distinctive Place Movie (88 Mb) Visual Homing Movie (15 Mb) |
P0.18 | Arnoud Visser |
| Tuesday 5/6 | 15.30-17.00 | ZS | Task 1: Endgames | P1.26 | no assistance |
| Wednesday 6/6 | 10.00-12.30 | P2 | Task 1: Endgames | P1.26 | Martijn Liem |
| Wednesday 6/6 | 13.00-15.00 | L2 | Quantative Navigation Lecture (pdf 473 Kb) |
P0.18 | Arnoud Visser |
| Wednesday 6/6 | 15.30-17.00 | ZS | Task 1: Endgames | P1.26 | no assistance |
| Thursday 7/6 | 10.00-12.30 | P3 | Task 1: Endgames | P1.26 | Martijn Liem |
| Thursday 7/6 | 13.00-17.00 | ZS | Task 1: Endgames | P1.26 | no assistance |
| Friday 8/6 | 10.00-12.30 | P4 | Task 1: Endgames | P1.26 | Martijn Liem |
| Friday 8/6 | 13.00-17.00 | ZS | Task 1: Endgames | P1.26 | no assistance |
Week 24
| date | time | type | subject | location | lecturer/assistant |
| Monday 11/6 | 10.00-12.30 | Pres | demonstration solution Task 1: Endgames | P1.26 | Martijn Liem |
| Monday 11/6 | 13.00-14.30 | L3 | path planning: algorithms | P0.18 | Leo Dorst |
| Monday 11/6 | 15.00-17.00 | P5 | Task 2: Path planning module Instruction | P1.26 | Olaf Booij |
| Tuesday 12/6 | 10.00-12.30 | P6 | Task 2: Path planning module | P1.26 | Olaf Booij |
| Tuesday 12/6 | 13.00-14.30 | L4 | rotations en homogeneous coördinates | P0.18 | Leo Dorst |
| Tuesday 12/6 | 15.30-17.00 | ZS | Task 2: Path planning module | P1.26 | no assistance |
| Wednesday 13/6 | 10.30-21.00 | Pres | Symposium Ambient Inteligence | Orpheus, Apeldoorn | voorverkoop (tot 6 juni korting) |
| Thursday 14/6 | 10.00-12.30 | ZS | Task 2: Path planning module | P1.26 | no assistance |
| Thursday 14/6 | 13.00-14.30 | L5 | kinematics: Denavit Hartenberg | P0.18 | Leo Dorst |
| Thursday 14/6 | 15.00-17.00 | ZS | Task 2: Path planning module | P1.26 | no assistance |
| Friday 15/6 | 10.00-12.30 | P7 | Task 2: Path planning module | P1.26 | Olaf Booij |
| Friday 15/6 | 13.00-14.30 | L6 | inverse kinematics | P0.18 | Leo Dorst |
| Friday 15/6 | 15.00-17.00 | ZS | Task 2: Path planning module | P1.26 | no assistance |
Week 25
| date | time | type | subject | location | lecturer/assistant |
| Monday 18/6 | 10.00-12.30 | P8 | Task 3: Inverse kinematics module | P1.26 | Olaf Booij |
| Tuesday 19/6 | 10.00-12.30 | P9 | Task 3: Inverse kinematics module | P1.26 | Olaf Booij |
| Wednesday 20/6 | 10.00-12.30 | P10 | Task 3: Inverse kinematics module | P1.26 | Olaf Booij |
| Thursday 21/6 | 10.00-12.30 | ZS | Task 3: Inverse kinematics module | P1.26 | no assistance |
| Friday 22/6 | 10.00-16.00 | Pres | integration and demonstration Task 2 and 3 | P1.26 | Olaf Booij |
| date | time | type | subject | location | lecturer/assistant | |
| Monday 25/6 | 10.00-12.00 | Experiment1 | Kick-Off | P1.26 | Arnoud Visser | Wednesday 27/6 | 10.00-12.00 | Experiment2 | Mid-Term | P1.26 | Arnoud Visser |
| Friday 29/6 | 10.20-14.40 | Experiment3 | Demonstration and Documentation | P1.26 | Arnoud Visser | schedule | -->
| Friday 29/6 | from 15.00 | Experiment4 | Barbecue | binnenplaats Diamandslijperij | VIA | |
| Friday 29/6 | from 22.00 | Experiment5 | Lustrum Feest | Catacomben | 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. The list of surveys of this year can be found in separate directory Experiment2007.
Here are the surveys of previous years:
- the surveys of the 2006 students, see Experiment2006
- the surveys of the 2005 students, see Experiment2005
- the surveys of the 2004 students, see Experiment2004
- Path-planning for a Hemisson-robot
- Path-planning for a Aibo-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)
You will be evaluated on your LabBook at the end of the week.
Results
The results can be found here.
-->
Evaluation
The course was overall evaluated by the participants with a 8.25.
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.
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 June 2007
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