headerphoto

About Search, Navigate and Actuate for the year 2013-2014

logo

You arived at the course page of "Search, navigate and actuate". This page is not in its final stage. Updates will follow without warning. See date of "last update".
This web-page is maintained by Toto van Inge ,Faculty of Science, University of Amsterdam

Introduction

The official description of course baiZSB6 is found in the (in Dutch) Studiegids. Even more information is given in the (in Dutch) Studiewijzer.
Also a Blackboard portal is available. Here you will find Leo Dorst's material.
See the tab at the top of the page labeled Lab Course for the tasks you should fulfill during the first three weeks.

During the last week, you work in a group on your own defined experiment.
Have a peek in the students their experiment papers from 2013-2004 listed here
The site of previous years can be found here.

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 DataNose, but in case of doubt use this page as reference.

Download Lecturnity Player for listening to lectures; synchronized with the sheets.

Week 23

Search

(follow_strategy.pl), (advice.pl)

date time type subject location lecturer/assistant
Monday 2/6 9.00-9.15 Intro Course Overview
Lecture pdf, recording lpd
SP C0.05 Toto van Inge
Monday 2/6 9.15-11.00 HC Searching through Game Trees - minimax and alpha-beta
Lecture pdf, recording minimax lpd, recording alpha-beta lpd.
SP C0.05 Toto van Inge fig22_3.txt
Monday 2/6 11:00-15:00 CP Task 0: Searching through Game Trees - Advice Language
for Tic-Tac-Toe lpd
Groep A - SP B1.24HIJ
Groep B - SP B1.24ABC
Tim van Rossum
Ysbrand Galama
fig22_5.txt
Monday 2/6 15:00-16:00 CP Task 0 + beoordelen Groep A - SP B1.24HIJ
Groep B - SP B1.24ABC
Ysbrand Galama
Tim van Rossum
Monday 2/6 16:00-17:00 CP Task 1 inlezen Groep A - SP B1.24HIJ
Groep B - SP B1.24ABC
Self Study
Tuesday 3/6 9.00-11.00 HC Path Planning algorithms SP F1.02 Leo Dorst
Tuesday 3/6 11.00-12.00 CP Task 1 Groep A - SP B1.24HIJ
Groep B - SP B1.24ABC
Self Study
Tuesday 3/6 12.00-16.00 CP Task 1 Groep A - SP B1.24HIJ
Groep B - SP B1.24ABC
Tim van Rossum
Nick de Wolf
Tuesday 3/6 16.00-17.00 CP Task 1 Groep A - SP B1.24HIJ
Groep B - SP B1.24ABC
Self Study
Wednesday 4/6 9.00-11.00 HC Qualitative Navigation
Lecture (pdf 1.1 Mb), recording (lpd 32 Mb)
Distinctive Place Movie (88 Mb)
Visual Homing Movie (15 Mb)
SP C0.110 Toto van Inge
Wednesday 4/6 11.00-12.00 PR Task 1 Group A: SP B1.24HIJ
Group B: SP G0.23-G0.25
self study
Wednesday 4/6 12.00-16.00 PR Task 1 Group A: SP B1.24HIJ
Group B: SP G0.23-G0.25
Casper van Houten
Ysbrand Galama
Wednesday 4/6 16.00-17.00 PR Task 1 Group A: SP B1.24HIJ
Group B: SP G0.23-G0.25
self study
Thursday 5/6 09.00-17.00 ZS Task 1 --------- self study
Friday 6/6 09.00-11.00 HC Quantative Navigation
Lecture (pdf 194 Kb), recording lpd, Voronoi graph movies.
SP G2.10 Toto van Inge
Friday 6/6 11.00-12.00 CP Task 1 Group A: SP A1.16
Group B: SP B1.24DEFG
Self Study
Friday 6/6 12.00-15.00 CP Task 1 Group A: SP A1.16
Group B: SP B1.24DEFG
Casper van Houten
Nick de Wolf
Friday 6/6 15.00-16.00 Pres demonstration student solutions Task 1: Endgames Group A: SP A1.16
Group B: SP B1.24DEFG
Casper van Houten
Nick de Wolf
Friday 6/6 16.00-17.00 CP Task 2 inlezen Group A: SP A1.16
Group B: SP B1.24DEFG
Self Study

Week 24

Navigate

date time type subject location lecturer/assistant
Monday 9/6 - - Tweede pinksterdag - -
Tuesday 10/6 9.00-11.00 HC rotations en homogeneous coordinates G2.10 Leo Dorst
Tuesday 10/6 11.00-12:00 CP Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Tuesday 10/6 12.00-16:00 CP Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Ysbrand Galama
Tim van Rossum
Tuesday 10/6 16.00-17.00 CP Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Wednesday 11/6 9.00-11.00 HC kinematics: Denavit Hartenberg Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Leo Dorst
Wednesday 11/6 11.00-12:00 PR Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Wednesday 11/6 12.00-16.00 ZS Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Nick de Wolf
Tim van Rossum
Wednesday 11/6 16.00-17.00 ZS Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Thursday 12/6 9.00-11.00 HC inverse kinematics G2.10 Leo Dorst
Thursday 12/6 11.00-12.00 CP Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Thursday 12/6 12.00-16.00 ZS Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Ysbrand Galama
Casper van Houten
Thursday 12/6 16.00-17.00 CP Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Friday 13/6 11.00-12.00 CP Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Friday 13/6 12.00-15.00 CP Task 2: Path planning module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Casper van Houten
Nick de Wolf
Friday 13/6 15.00-16:00 Pres demonstration student solutions Task 2: Endgames G0.10-G0.12 Casper van Houten
Nick de Wolf
Friday 13/6 16.00-17.00 CP Task 3 inlezen Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study

Week 25

Actuate

date time type subject location lecturer/assistant
Monday 16/6 9.00-17.00 CP Task 3: Inverse kinematics module --------- Self Study
Tuesday 17/6 9.00-10.00 CP Task 3: Inverse kinematics module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Tuesday 17/6 10.00-16.00 CP Task 3: Inverse kinematics module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Ysbrand Galama
Tim van Rossum
Tuesday 17/6 16.00-17.00 CP Task 3: Inverse kinematics module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Wednesday 18/6 9.00-11.00 Exp Brains session for next week group projects Group A+B: SP G0.10-G0.12 Toto van Inge
Wednesday 18/6 11.00-15.00 CP Task 3: Inverse kinematics module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Tim van Rossum
Nick de Wolf
Wednesday 18/6 15.00-17.00 CP Task 3: Inverse kinematics module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Thursday 19/6 9.00-10.00 CP Task 3: Inverse kinematics module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Thursday 19/6 10.00-16.00 CP Task 3: Inverse kinematics module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Casper van Houten
Ysbrand Galama
Thursday 19/6 16.00-17.00 CP Task 3: Inverse kinematics module Group A: SP G0.23-G0.25
Group B: SP G0.10-G0.12
Self Study
Friday 20/6 9.00-10.00 CP Task 3: Inverse kinematics module Group A: SP G0.23-G0.25
Group B: SP G0.18
Self Study
Friday 20/6 10.00-15.00 Pres demonstration student solutions Task 3: Endgames Group A: SP G0.23-G0.25
Group B: SP G0.18
Casper van Houten
Nick de Wolf
Friday 20/6 15.00-17.00 Exp Kick-Off Group A+B: SP G0.18 Toto van Inge

Week 26

Go, where no one has gone before

It is not the final result that counts, but your summery of your survey. Document your progress, experiments and decisions of your practical work and experiment in a Paper.

The knowledge gained during this year and especially during the last three weeks, you can now explore new possibilities.

Here are some suggestions:

  • Path-planning for a Hemisson-robot
  • Talking mouth for a Aibo-robot
  • Maze navigation with a Nao-robot
  • Looking to a talking person with a Nao-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)
  • WiiBot RTX UMI
  • Solve chess endgame with Monte Carlo tree search (MCTS)

It is recommended to work in groups of three or four students. However, the groups size should fit the load of the proposed experiment.

date time type subject location lecturer/assistant
Monday 23/6 9.00-10.00 Exp Group A: SP B1.24HIJ
Group B: SP B1.24ABC
Self Study
Monday 23/6 10.00-16.00 Exp Group A: SP B1.24HIJ
Group B: SP B1.24ABC
??
??
Monday 23/6 16.00-17.00 Exp Group A: SP B1.24HIJ
Group B: SP B1.24ABC
Self Study
Tuesday 24/6 9.00-10.00 Exp Group A: SP B1.24HIJ
Group B: SP B1.24ABC
Self Study
Tuesday 24/6 10.00-16.00 Exp Group A: SP B1.24HIJ
Group B: SP B1.24ABC
??
??
Tuesday 24/6 16.00-17.00 Exp Group A: SP B1.24HIJ
Group B: SP B1.24ABC
Self Study
Wednesday 25/6 9.00-10.00 Exp Group A: SP G0.23-G0.25
Group B: SP G0.18
Self Study
Wednesday 25/6 10.00-16.00 Exp Group A: SP G0.23-G0.25
Group B: SP G0.18
??
??
Wednesday 25/6 16.00-17.00 Exp Group A: SP G0.23-G0.25
Group B: SP G0.18
Self Study
Thursday 26/6 9.00-10.00 Exp Group A: SP F2.04
Group B: SP G0.18
Self Study
Thursday 26/6 10.00-16.00 Exp Group A: SP F2.04
Group B: SP G0.18
??
??
Thursday 26/6 16.00-17.00 Exp Group A: SP F2.04
Group B: SP G0.18
Self Study
Friday 27/6 9:00~13.00 Exp Demonstrations and Paper Group A: SP G0.23-G0.25
Group B: SP G0.18
Toto van Inge
Casper van Houten
Nick de Wolf
Ysbrand Galama
Tim van Rossum
Friday 27/6 about 17.00 Exp Barbecue near canteen VIA

Evaluation

Follow the links to find guidance on writing a LabBook and a paper.

You will be evaluated on your LabBooks (see: LabBook criteria) and on your paper (see: Paper criteria).

Literature

For the implementation in prolog we will look at chapter 24 of Prolog Programming for Artificial Intelligence by Ivan Bratko. The companion website of the 4th edition is not yet available, the companion website of the 3th edition contains several student resources. 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 of the book was in the previous years explored in the course Reactive Behaviours. Now this course is replaced the more advanced course Probabibilistic Robotics / Autonomous Mobile Robots. Murphy's book is not longer required, and should not be bought. The two chapters are available electronically( Chapter 9 and Chapter 10).

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 KI Bachelors were not schooled at Dutch Universities, a different course was given with another focus. Still, much can be learned from the course 'Robotica' 2003 A.D.

The origin of this course is even older: 'Robotica' 1988 A.D. In that early period I made the decision to purchase a robot arm: the UMI rtx. It is the one still alive in the current course!