Advanced Artificial Intelligence (Winter 2008)

From GICL Wiki
Revision as of 18:03, 17 March 2009 by GICL Bot (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.



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:

indoor experimental layout (not drawn to scale)

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


Trial Runs A-D

This new dataset gathers more signal strength data. In doing so, the format of the files change slightly. There are more details in the README file enclosed in the datasets.

The robot is in the same environment at the same starting location. Only the speeds, and path it follows changes.

There are 4 trial runs here:

  • Trial A:
  • Trial B:
    • Stop 'n Go: travel at 100mm/s for 4m, stop for 20 seconds, repeat for ~60m.
  • Trial C:
    • Variable Speeds: The robot travels at varying speeds, sometimes stopping and moving backward. The total distance traveled is ~60m.
  • Trial D:

The simple pattern (not drawn to scale)

Outdoor Trial Runs A-D

This final dataset repeats the previous 4 trial runs outdoors and includes GPS positional data. When viewing the data in a mapping tool such as Google Earth, you will see the GPS positions are also noisy due to the short distance traveled. It is possible to incorporate this data into your work.

The outdoor scenario pattern

The format of the GPS data is located in the README.txt. There is also a KML file containing the router positions (the lat/lon info is there too).


Parsed GPS data : We parsed the gps data to create a CSV of just the LAT/LON positions and then fed it into GPS Visualizer to create Google Earth tracks of these experiments.

GPS Plotted data

Path-Loss Model

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 n and c.

 L = 10 * n log(d) +c


  • L : the signal strength
  • d : the distance between transmitter and receiver

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 and fitting a known function to that data. A plotting tool such as GnuPlot can easily perform this task.


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.

Alternative Dataset and Programming Assignment

You are provided with a dataset gathered on Drexel University's Campus. The dataset consists of two log files from KISMET, showing a GPS-enabled tour of campus with associated Wireless Access points from the Dragonfly network.

The problem: use this dataset to implement a particle filter (or other technique) that would help users locate where the are on Drexel's campus based on data about the RSSI from access points within radio range.

Run this on campus, generate log data of your _estimated_ position based on the prediction technique.

If you believe the results are looking promising, you'll be provided with a GPS card so you can perform validation of the work and estimate error over time.

The Drexel-GPS-AP dataset.

Useful Resources

Some code here may be useful to you...