Advanced Artificial Intelligence (Winter 2008)

Revision as of 16:28, 19 February 2008

This is the page for Advanced AI for Winter 2008

Dr. Regli's Office Hours are 14:00-15:00 M-W, right before class.

The syllabus for the course is available here.

Homeworks

Homework #1 is available here.

Homework #2 is available here.

Homework #3 is available here.

Lecture slides

Lecture Unit 1: Introduction to Uncertainty.

Lecture Unit 2: Bayes Nets (Ch 14 from R&N).

Lecture Unit 3: Inference in Bayes Nets (Ch 14 from R&N).

Lecture Unit 4: Kalman Filtering (Not from R&N).

Lecture Unit 5: Particle Filtering (Not from R&N).

Lecture Unit 6: Temporal Probability (Ch 15 from R&N).

Example of the Dishonest Casino (Dynamic Bayes Nets).

Programming Assignment

The programming assignment is going to be given out in 2-phases. The first phase is empirical and experimental. The objective of which is to encourage students to experiment with a number of the techniques taught in the class and employ them in creative ways against a real-world dataset. This is not a toy problem, but an open-ended assignment intented to require creativity on the part of the student. Students are expected to look at the data and scenario and then, using the techniques taught in the class thus far (or look ahead, if you so desire), identify ways in which these techniques might be applied to deduce about properties of the world.

The domain of the problem is wireless networking and localization of a mobile robot using RF information. This is a current area of commercial, military and academic interest. The key questions here are:

• How can a person or a robot figure out its location without resorting to GPS?
• OR: if we have GPS, how can I figure out where I am if I'm inside or in a GPS-denied environment?

Scenario Description

Pioneer3 All-Terrain robot with computer and wireless intefaces

The data sets consist of RSSI information acquired from 4 fixed routers as a robot moves in an open (LoS) environment. The robot has two network cards, hence there are two different sensors for reading the RSSI information. The spreadsheets break this information out by timestamp and include an estimate of the robot's location based on its odometer readings. In several cases there is an analytic computation of the robot's actual location that compensates for drift in the odometer readings (this was computed by looking at the robot's location on the floor). In some experiments the robot moves in a straight line, in others is does not. In some experiments the robot moves with constant velocity, in others it stops and pauses in spots. These motion patterns are evident in the data.

Trial run 1-3:

This dataset contains three trial runs of an indoor experiment, 4 routers. In each of the experiments the starting point of the robot is at location (2.51m, 5.71m). The robot is instructed to travel 4m then stop for some time, then continue moving forward 4m. The repeats this 15 times. The main logfile that contains the RSSI readings and the robot odometry readings is in the file: p3at-YYYYMMDD-HHMMSS.log and further broken down into separate odometry and signal strength readings for each wireless card interface. Furthermore, trial runs two and three contains a actual_mm.txt which contains ground-truth locations of the stopping points (measured by hand).

The format of the files are:

<timestamp in ms> odom <curr speed> <x pos in mm> <y pos in ms> <heading in degrees>
<timestamp in ms> <interface> <ssid> <bssid> <signal> <noise>

The individual trial runs were set up as follows:

• Trial 1:
  • Robot traveled from the starting point at (2.51m, 5.71m) near router01 to approximately (52m, 7.6m) from the origin.
  • Robot drove straight toward router02.
  • Note, the robot therefore drifted 2m to the right (relative to the robot heading), and about 10m less than it should have.
  • Traveled 4 meters at 75mm/s, stopped for about 2 seconds, then traveled again 4m. Repeat 15 times.
  • Two wireless interfaces.
• Trial 2:
  • Prior to performing the trial run we re-calibrated the robot's odometry.
  • Traveled 4 meters at 100mm/s, stopped for 10 seconds, then traveled forward
  • Three wireless interfaces.
• Trial 3:
  • there were less RSSI readings
  • Stopped for 20 seconds every 4 meters
  • Three wireless interfaces.

There are more detailed descriptions of the log file formats and experimental set-up in experiments/20080204-T1/README.txt and experiments/README.txt

THE DATASET

Wireless Network Power information

To use the RSSI information in the log files in a path-loss model equation (for example), it would be necessary to find the coefficients

<math>n</math> and <math>c</math>. <math>L = 10\cdot n \log(d) +c</math>

One method is to use a fitting algorithm, such as least squares fitting, and the given signal strength data to determine the coefficients. This is done by plotting the true locations versus the signal strength readings. A plotting tool such as GnuPlot can easily perform this task.

PHASE I: ASSIGNMENT FOR FRIDAY FEB 22

Examine the data and develop ideas about what kinds of questions might be answered about it using the techniques covered in the class. Examples of such inquiries include:

-- Use a Kalman filter to improve the robot's estimation of RSSI by fusing the inputs from both NICS

-- Determine if the distribution of RSSI data is Gaussian (or how close to Gaussian is it)?

-- Develop a HMM or Dynamic Bayes net that could tell if the robot is moving given RSSI readings.

-- Bound the error of the RSSI readings.

-- Fuse the RSSI readings with information about distance, odometery and electro-magnetic path loss to get an estimate of the error rate/sensitivity of the NIC's RSSI sensors.

-- Perform trilateration to estimate the position of the robot.

-- Fuse the trilateration data with a kalman filter to improve estimates of location over time.

-- Apply a particle filter to the RSSI data.

-- Figure out (map?) the locations of the access points as you move around. i.e. build up a belief about where they are, how far away they are, etc. Much like mapping an environment.

... and others. The above are just meant as ideas. You are welcome to come up with others or suggest alternatives to the above.

You are to implement, download or otherwise find code for the above techniques and any others that you may find useful. Experiment with this code on the data and assess what kinds of questions might you be able to answer and what would be the steps in reasoning to obtain these answers. How accurate might you be able to get for certain questions?

Write up your experiences (1-to-3 pages) and recommendations (typeset reports only, no hand written reports); document any and all software you use, experiments you perform or results you find.

This is a somewhat open-ended assignment that will emphasize creativity on the part of the student.

Useful Resources

http://www.ibm.com/developerworks/opensource/library/os-wirelesssitesurvey/?S_TACT=105AGX54&S_CMP=B0215&ca=dnw-906

http://en.wikipedia.org/wiki/RCPI

http://en.wikipedia.org/wiki/Trilateration

http://en.wikipedia.org/wiki/Triangulation

http://en.wikipedia.org/wiki/Log_Distance_Path_Loss_Model

http://en.wikipedia.org/wiki/Path_loss

Some code here may be useful to you...

http://robots.stanford.edu/cs226-06/data.html

http://www.openslam.org/