## This is the information of year 2011.

The site of the previous year can be found here.
The site of the next 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. Blackboard is mainly used for email and grading.

### 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

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

Search
 date time type subject location lecturer/assistant Monday 30/5 11.00-11.15 L0 Course Overview Lecture ppt, recording lpd G0.18 Arnoud Visser Monday 30/5 11.15-13.00 SCR1 Searching through Game Trees - minimax and alpha-beta Lecture ppt, recording minimax lpd, recording alpha-beta lpd. G0.18 Arnoud Visser fig22_3.txt Monday 30/5 13.30-15:00 SCR2 Searching through Game Trees - Advice Language Lecture ppt, recording Advice Language for Tic-Tac-Toe lpd G0.18 Arnoud Visser fig22_5.txt Tuesday 31/5 11.00-13.00 P1 Task 1: Endgames G0.18 Arnoud Visser Tuesday 31/5 13.30-15.00 L1 Qualitative NavigationLecture (pdf 1.1 Mb), recording (lpd 32 Mb)Distinctive Place Movie (88 Mb)Visual Homing Movie (15 Mb) G0.18 Arnoud Visser Tuesday 31/5 15.00-17.00 ZS Task 1: Endgames G0.18 no assistance Wednesday 1/6 11.00-13.00 P2 Task 1: Endgames G0.18 Arnoud Visser Wednesday 1/6 13.30-15.00 L2 Quantative NavigationLecture (pdf 194 Kb), recording lpd, Voronoi graph movies. P0.18 Arnoud Visser Wednesday 1/6 15.00-17.00 ZS Task 1: Endgames G0.18 no assistance Thursday 2/6 11.00-17.00 Ascension Day Friday 3/6 11.00-17.00 Day after Ascension Day

Navigate
 date time type subject location lecturer/assistant Monday 6/6 10.00-12.00 L3 Path Planning algorithms G0.18 Leo Dorst Monday 6/6 12.00-14:00 P3 Task 1: Endgames G0.18 Arnoud Visser Monday 6/6 14.00-17.00 ZS Task 1: Endgames G0.18 no assistance Tuesday 7/6 10.00-12.00 L4 rotations en homogeneous coordinates G0.18 Leo Dorst Tuesday 7/6 12.00-14.00 P4 Task 1: Endgames G0.18 Arnoud Visser Tuesday 7/6 14.00-17.00 ZS Task 1: Endgames G0.18 no assistance Wednesday 8/6 10.00-12.00 L5 kinematics: Denavit Hartenberg G0.18 Leo Dorst Wednesday 8/6 12.00-17.00 Pres Schedule demonstration student solution G0.18 Julian Kooij Thursday 9/6 10.00-12.00 L6 inverse kinematics G0.18 Leo Dorst Thursday 9/6 12.00-14.00 P5 Task 2: Path planning module G0.18 Julian Kooij Thursday 9/6 14.00-17.00 ZS Task 2: Path planning module G0.18 no assistance Friday 10/6 10.00-12.00 No Lecture Friday 10/6 12.00-14.00 P6 Task 2: Path planning module G0.18 Julian Kooij Friday 10/6 14.00-17.00 ZS Task 2: Path planning module G0.18 no assistance

Actuate
 date time type subject location lecturer/assistant Monday 13/6 9.00-17.00 Whit Day Tuesday 14/6 9.00-17.00 P7 Task 3: Inverse kinematics module G0.18 Julian Kooij Wednesday 15/6 9.00-17.00 P8 Task 3: Inverse kinematics module G0.18 Julian Kooij Wednesday 15/6 11.00-13.00 Experiment0 Brainstorming next week G0.18 Arnoud Visser Thursday 16/6 9.00-17.00 P9 Task 3: Inverse kinematics module G0.18 Julian Kooij Friday 17/6 9.00-17.00 Pres demonstration and integration Task 2 and 3 G0.18 Julian Kooij

Go, where no one has gone before.
 date time type subject location lecturer/assistant Monday 20/6 9.00-12.00 Experiment1 Kick-Off G0.18 Arnoud Visser Monday 20/6 12.00-17.00 ZS G0.18 no assistance Tuesday 21/6 9.00-17.00 ZS G0.18 no assistance Wednesday 22/6 9.00-12.00 Experiment2 Mid-Term G0.18 Arnoud Visser Wednesday 23/6 12.00-17.00 ZS G0.18 no assistance Thursday 23/6 9.00-17.00 ZS G0.18 no assistance Friday 24/6 9:00-17.00 Experiment3 Demonstration and Documentation G0.18 Arnoud Visser Friday 24/6 from 17.00 Experiment4 Barbecue near cantine 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 the previous years:

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

## 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. Now this course is replaced the more advanced course Probabibilistic Robotics. 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 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 May 31, 2012

#### This web-page and the list of participants to this course is maintained by Arnoud Visser (arnoud@science.uva.nl)Faculty of ScienceUniversity of Amsterdam

 visitors in arnoud@science.uva.nl