Course Search, Navigate, and Actuate

"Zoeken, Sturen en Bewegen"

This is the information of year 2009.

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.

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

Search
(follow_strategy.pl), (advice.pl)
date time type subject location lecturer/assistant
Monday 1/6 Whit Monday Holiday
Tuesday 2/6 10.00-10.15 L0 Course Overview
Lecture ppt
P1.26 Arnoud Visser
Tuesday 2/6 10.15-12.00 SCR1 Searching through Game Trees - minimax and alpha-beta
Lecture ppt
P1.26 Arnoud Visser fig22_3.txt
Tuesday 2/6 13.00-14.30 SCR2 Searching through Game Trees - Advice Language
Lecture ppt
P1.26 Arnoud Visser fig22_5.txt
Wednesday 3/6 10.00-12.00 P1 Task 1: Endgames P1.26 Julian Kooij
Wednesday 3/6 12.00-12.45 L1 Qualitative Navigation
Lecture (pdf 1.1 Mb)
Distinctive Place Movie (88 Mb)
Visual Homing Movie (15 Mb)
C3.02 Arnoud Visser
Wednesday 3/6 13.00-13.45 L2 Quantative Navigation
Lecture (pdf 473 Kb)
C3.02 Arnoud Visser
Wednesday 3/6 13.30-17.00 ZS Task 1: Endgames P1.26 no assistance
Thursday 4/6 10.00-12.00 P2 Task 1: Endgames P1.26 Julian Kooij
Thursday 4/6 12.00-13.30 Lecture already given GS.01A Arnoud Visser
Thursday 4/6 12.30-17.00 ZS Task 1: Endgames P1.26 no assistance
Friday 5/6 10.00-13.00 P4 Task 1: Endgames P1.26 Julian Kooij
Friday 5/6 13.00-17.00 ZS Task 1: Endgames P1.26 no assistance

Week 24

Navigate
date time type subject location lecturer/assistant
Monday 8/6 10.00-16.30 Pres demonstration student solution Task 1: Endgames P1.26 Julian Kooij
Monday 8/6 13.00-14.30 NO LECTURE
Tuesday 9/6 10.00-12.30 P5 Task 2: Path planning module P1.26 Julian Kooij
Tuesday 9/6 13.00-14.30 L3 Path Planning algorithms B2.40 Leo Dorst
Tuesday 9/6 15.30-17.00 ZS Task 2: Path planning module P1.26 no assistance
Wednesday 10/6 10.00-12.30 P6 Task 2: Path planning module P1.26 Julian Kooij
Wednesday 10/6 13.00-14.30 L4 rotations en homogeneous coordinates C3.02 Leo Dorst
Wednesday 10/6 15.30-17.00 ZS Task 2: Path planning module P1.26 no assistance
Thursday 11/6 10.00-12.30 P7 Task 2: Path planning module P1.26 Julian Kooij
Thursday 11/6 13.00-14.30 L5 kinematics: Denavit Hartenberg P0.19 Leo Dorst
Thursday 11/6 13.00-17.00 ZS Task 2: Path planning module P1.26 no assistance
Friday 12/6 10.00-12.30 P7 Task 2: Path planning module P1.26 Julian Kooij
Friday 12/6 13.00-14.30 L6 inverse kinematics P0.14 Leo Dorst
Friday 12/6 14.30-16.30 ZS Task 2: Path planning module P1.26 no assistance

Week 25

Actuate
date time type subject location lecturer/assistant
Monday 15/6 10.00-12.30 P8 Task 3: Inverse kinematics module P1.26 Julian Kooij
Monday 15/6 12.30-16.30 ZS Task 3: Inverse kinematics module P1.26 no assistance
Tuesday 16/6 10.00-16.30 ZS Task 3: Inverse kinematics module P1.26 no assistance
Wednesday 17/6 10.00-12.30 P9 Task 3: Inverse kinematics module P1.26 Julian Kooij
Wednesday 17/6 12.30-16.30 ZS Task 3: Inverse kinematics module P1.26 no assistance
Thursday 18/6 10.00-12.30 ZS Task 3: Inverse kinematics module P1.26 no assistance
Friday 19/6 10.00-16.00 Pres integration and demonstration Task 2 and 3 P1.26 Julian Kooij

Week 26

Go, where no one has gone before.
date time type subject location lecturer/assistant
Monday 22/6 10.00-12.00 Experiment1 Kick-Off P1.26 Arnoud Visser
Monday 22/6 12.30-16.30 ZS P1.26 no assistance
Tuesday 23/6 10.00-17.00 P1.26 no assistance
Wednesday 24/6 10.00-12.00 Experiment2 Mid-Term P1.26 Arnoud Visser
Wednesday 24/6 12.30-16.30 ZS P1.26 no assistance
Thursday 25/6 10.00-17.00 P1.26 no assistance
Friday 26/6 10.20-15.40 Experiment3 Demonstration and Documentation P1.26 Arnoud Visser
Friday 26/6 from 17.00 Experiment4 Barbecue 'terras' tussen gebouw A en B 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 this and previous years:

Here are some suggestions:
  • 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)
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 8.4 .

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.


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. This 1th year course is replaced by the 3rd year course Probabibilistic Robotics. Murphy's book is not longer required.

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 June 23 2009

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