O Opleiding Kunstmatige Intelligentie - Zoeken, Sturen en bewegen`

Home   Actueel   Over de FNWI   Onderwijs   Onderzoek   Voorzieningen   Zoeken


Opleiding AI
Onderwijsmededelingen

Blackboard Courses
StudieWeb
WebMail

Course Search, Navigate, and Actuate

"Zoeken, Sturen en Bewegen"

This is the information of year 2006

The site of the previous year 2005 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

Week 23

Search
date time type subject location lecturer/assistant
Monday 5/6 Whit Monday
Tuesday 6/6 10.00-10.15 SCR1 Course Overview
Lecture(pdf 182 Kb)		 P1.26 Arnoud Visser
Tuesday 6/6 10.15-12.00 SCR2 Searching through Game Trees - minimax and alpha-beta(pdf 226 Kb) P1.26 Arnoud Visser
Tuesday 6/6 12.30-14.30 SCR3 Searching through Game Trees - Advice Language (pdf 226 Kb) P1.26 Arnoud Visser
Wednesday 7/6 10.00-12.30 P1 Endgames P1.26 Stef Post
Wednesday 7/6 13.00-15.00 L1 Qualitative Navigation
Lecture (ppt 427 Kb)(pdf 408 Kb)
Movie (88 MB)		 P2.27 Arnoud Visser
Wednesday 7/6 15.30-17.00 L2 Quantative Navigation
Lecture (126 Kb)		 P2.27 Arnoud Visser
Thursday 8/6 10.00-12.00 L3 path planning: algorithms P2.27 Leo Dorst
Thursday 8/6 13.00-15.00 L4 rotations en homogeneous coördinates P2.27 Leo Dorst
Thursday 8/6 15.30-17.00 P2 Endgames P1.26 Stef Post
Friday 9/6 10.00-12.00 L5 kinematics: Denavit Hartenberg P2.27 Leo Dorst
Friday 9/6 13.00-15.00 L6 inverse kinematics P2.27 Leo Dorst
Friday 9/6 15.00-17.00 P1.26 self-study

Week 24

Navigate
Endgames
date time type subject location lecturer/assistant
Monday 12/6 10.00-12.30 P3 Endgames P1.26 Stef Post
Monday 12/6 13.00-17.00 P3 Endgames P1.26 no assistance
Tuesday 13/6 10.00-12.30 P4 Endgames P1.26 Stef Post
Tuesday 13/6 13.00-15.00 P4 demonstration solution Endgames P1.26 Stef Post
Wednesday 14/6 10.00-12.30 P5 highPath P1.26 Olaf Booij
Wednesday 14/6 13.00-17.00 P5 highPath P1.26 self-study
Thursday 15/6 10.00-12.30 P6 highPath P1.26 Olaf Booij
Thursday 15/6 13.00-17.00 P6 highPath P1.26 self-study
Friday 16/6 10.00-12.30 P7 path to garbage P1.26 Olaf Booij
Friday 16/6 13.00-17.00 P7 path to garbage P1.26 self-study

Week 25

Actuate
date time type subject location lecturer/assistant
Monday 19/6 10.00-12.30 P8 lowPath P1.26 self-study
Tuesday 20/6 10.00-12.30 P9 lowPath P1.26 Olaf Booij
Wednesday 21/6 10.00-12.30 P10 inverse kinematics P1.26 Olaf Booij
Thursday 22/6 10.00-12.30 P11 inverse kinematics P1.26 Olaf Booij
Friday 23/6 10.00-16.00 P12 integration and demonstration P1.26 Olaf Booij

Week 26

Go, where no one has gone before.

his time it is not the result that counts, but your summery of your survey. Document your progress, experiments and decisions in a LabBook.

date time type subject location lecturer/assistant
Monday 26/6 10.00-12.00 Experiment1 Kick-Off P1.26 Arnoud Visser
Wednesday 28/6 10.00-12.00 Experiment2 Mid-Term P1.26 Arnoud Visser
Friday 30/6 10.15-15.45 Experiment3 Demonstration and Documentation P1.26 Arnoud Visser
Friday 30/6 9.00-13.00 Experiment4 2th year project presentations P.017 Theo Janssen
Friday 30/6 13.30-17.00 Experiment5 3th year project presentations A.B. Bert Bredeweg
Friday 30/6 from 17.00 Experiment6 Barbecue binnenplaats Diamandslijperij VIA

With a working system, and the acquired knowledge, you can explore new possibilities. Until now, the following ideas came up:

  • FingerFootball
  • Huge Stearable WebCam
  • A* path-planning for a Dutch Junior Rescue Robot
  • Play Four-at-Row
  • ChatBot on a Kid's keyboard
  • TetrisAI with the generation of Minkowksi sums.
Here are the selections of different years: Here are some other suggestions:
  • Path-planning for a Hemisson-robot
  • Path-planning for a Aibo-robot
  • Play on a tilted board
  • Play on a NewChess board
  • Extend the checkmate problem to more complex situations
  • Create 2D Game-interface with GameMaker.
It is recommanded to work in groups of three students.

You will be evaluated on your LabBook at the end of the week.

Evaluation

The course was overall evaluated by the participants with a 7.92.

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 29 June 2006

o 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

visitors in arnoud@science.uva.nl