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 OR-nodes, because we have only to make one winning move. Their positions are represented as AND-nodes, 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
  • alpha-beta 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 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 31/5	Whit Monday
Tuesday 1/6	10.00-10.15	L1	Course Overview Lecture (614 Kb)	Studio Classroom - Amstel Instituut, Kruislaan 404	Arnoud Visser
Tuesday 1/6	10.15-12.00	L1	Problem Decomposition and AND/OR Graphs	Studio Classroom - Amstel Instituut, Kruislaan 404	Maarten van Someren
Tuesday 1/6	12.30-14.30	W1	decomposition problems	Studio Classroom - Amstel Instituut, Kruislaan 404	Maarten van Someren
Tuesday 1/6	15.00-17.00	L2	the minimax principle and the alpha-beta algorithm	Studio Classroom - Amstel Instituut, Kruislaan 404	Maarten van Someren
Wednesday 2/6	10.00-12.30	P1	Checkmate	P.126	Matthijs Spaan, Coen Pieterse
Wednesday 2/6	13.00-15.00	L4	Qualitative Navigation Lecture (461 Kb) Movie (88 MB)	P.017	Arnoud Visser
Wednesday 2/6	15.30-16.30	W2	introduction Dataconversion	Studio Classroom - J.302 Valckenierstraat 65	Matthijs Spaan, Coen Pieterse
Thursday 3/6	10.00-12.30	P1	Checkmate	P.126	Matthijs Spaan, Coen Pieterse
Thursday 3/6	13.00-15.00	L5	Quantative Navigation Lecture (126 Kb)	P.017	Arnoud Visser
Friday 4/6	10.00-12.30	P2	A* in Java	P.126	Matthijs Spaan, Coen Pieterse

Week 24

date	time	type	subject	location	lecturer/assistant
Monday 7/6	10.00-12.30	P3	high path	P.126	Matthijs Spaan, Coen Pieterse
Monday 7/6	13.00-15.00	self-study	path planning: Cspace
Tuesday 8/6	10.00-12.30	P3	high path	P.126	Matthijs Spaan, Coen Pieterse
Tuesday 8/6	13.00-15.00	self-study	path planning: structure
Wednesday 9/6	10.00-12.30	P4	path to garbage	P.126	Matthijs Spaan, Coen Pieterse
Wednesday 9/6	13.00-15.00	L8	path planning: algorithms	P.017	Leo Dorst
Thursday 10/6	10.00-12.30	P5	low path	P.126	Matthijs Spaan, Coen Pieterse
Thursday 10/6	13.00-15.00	L9	rotations en homogeneous coördinates	P.017	Leo Dorst
Friday 11/6	'open dag op locatie'

Week 25

Monday 14/6	10.00-12.30	P6	kinematics	P.126	Matthijs Spaan, Coen Pieterse
Monday 14/6	13.00-15.00	L11	kinematics: Denavit Hartenberg	P.017	Leo Dorst
Tuesday 15/6	10.00-12.30	P6	kinematics	P.126	Matthijs Spaan, Coen Pieterse
Tuesday 15/6	13.00-15.00	L12	inverse kinematics	P.017	Leo Dorst
Wednesday 16/6	10.00-12.30	P7	inverse kinematics	P.126	Matthijs Spaan, Coen Pieterse
Friday 18/6	10.00-16.00	P8	integration and demonstration	Robotlab - F1.21, Kruislaan 403	Matthijs Spaan

Week 26

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.00-12.00	Experiment1	Kick-Off	P.126	Arnoud Visser
Wednesday 24/6	10.00-12.00	Experiment2	Mid-Term	P.126	Arnoud Visser
Friday 26/6	10.00-13.30	Experiment3	Demonstration and Documentation	Robotlab - F1.21, Kruislaan 403	Arnoud Visser
Friday 26/6	14.00-17.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 alpha-beta algorithm
• Use an Aibo as webcam
• Let the Aibo move one piece
• Create a 8x8 maze for the Aibo
• Create a maze for a plotter-robot
• Create 2D Game-interface with GameMaker.

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'.