Signals

Purpose

The purpose of this page is to showcase some of the projects that I worked on while I was taking CS 6601 : Artificial Intelligence at Georgia Tech during the Spring 2011 semester.  You will find my short descriptions of the projects listed below, as well as links to the full papers that I wrote for each project.

About Me

I’m an Electrical Engineering PhD student at the Georgia Institute of Technology where I specialize in Control Theory and Robotics.  I am also a Research Engineer at the Georgia Tech Research Institute (GTRI).

Reading and Assignments

In the course, we completed 7 assignments on the foundations of AI, after reading the relevant material in the textbook. The first assignment I completed centered around an introduction of Search. While in the past, I had explored binary search trees and other common search algorithms, I had only heard of the search algorithms I encountered in this assignment, such as A*, D*, and D* Lite. Luckily, this AI course gave me the opportunity to study these algorithms and their use of heuristics to narrow the search space and reduce the search time. The of a heuristic cost function to improve search interested me so much that I had to focus my first mini-project around A* for path planning. The second assignment involved Constraint Satisfaction Problems (CSPs) where the problem is solved when each variable in the problem has a value that meets the criteria specified. CSPs decrease solution times by determining states that infringe upon the problem constraints, which eliminates large portions of the state space. In the CSP assignment, I made use of backtracking with conflict-directed back jumping to efficiently solve a graph coloring problem. I learned about Propositional Logic, Conjunctive Normal Form (CNF), inference, and unicorns in the third assignment. I plan on delving more into Prolog and it’s uses when I have more time over the summer. The fourth assignment was when we began to model uncertainty with Bayes Nets and probabilistic terms.

I spent the most time on the Natural Language Processing (NLP) assignment because I enjoyed it the most. The first problem involved taking a monolingual corpus and breaking the body of words into unigrams, bigrams, and trigrams. I decided to use a text version of the King James Bible for the corpus and I used the Python programming language to parse the text. After the script broke the King James Bible into the three language models, I used a random selection of the most common phrases to generate my own text. Here is a selection of the generated text from the trigram model:

“And it came and he said LORD of hosts before the LORD and the LORD of the children the name of thus saith the midst of the name of the Lord GOD and I will the midst of the land of and all the before the LORD and all the unto the LORD.”

Skills: Mini-projects

There were three mini-projects in which I chose to research a problem that was supposed to be relevant to my your future career. For each of these three projects, I proposed a solution, implemented it, and described it in a mini-conference paper.

Autonomous Underwater Vehicle Path Planning: A Comparison of A* and Fast Marching Method (PDF)

In the first Mini-Project, I compared three different search algorithms for robotic path planning. Using Octave, a Matlab clone, I implemented D*, A*, and the Fast Marching Method (FMM) search algorithms to move an agent from an initial position to a final goal state. I learned a great deal about heuristic functions for 2D state spaces, such as using a combination of the Manhattan and diagonal Distances. I am going to be exploring the implementation of the FMM on an actual autonomous underwater vehicle in the future.

A* Search

D* Search

Dynamic Re-Planning in Multi-Agent Networks(PDF)

In the second Mini-Project, I implemented a multi-agent system that made use of the Contract Net Protocol (CNP) to allocate dynamically generated tasks. I wrote the CNP within the Mission Oriented Operating Suite (MOOS) so that it could be tested in simulation and hopefully tested on actual underwater vehicles in the future. MOOS is a popular publish-and-subscribe architecture for autonomous surface and underwater vehicles.  Here is a video of the MOOS simulation:

Simulation of EKF-Localization in a 2D Environment(PDF)

The final Mini-Project was my favorite project. In this project, I wrote an Extended Kalman Filter (EKF) to account for error in the dead reckoning odometry data of a wheeled robot. I implemented the EKF-Localization algorithm within the publish-and-subscribe Robot Operating System (ROS), which allowed me to simulate the filter in Player/Stage. This summer, the EKF-Localization algorithm will be implemented on the Seekur Jr. Below you will find a full description of the project as well as a video of the ROS EKF simulation.

Problem Addressed and Its Importance

EKF ROS Simulation

In order for an autonomous system to make informed decisions, it must have knowledge of its environment and its state within the environment. For example, if a robot is instructed to carry an item to a specific room in a building, the robot must have knowledge of its current location in order to plan an efficient route. Likewise, a robot cannot inform safety crews of the location of hazardous materials if the robot itself does not know its current location. However, in order for the robot to localize itself, it also needs previously constructed maps to correlate observed landmarks to landmarks described in the maps. It was determined that the problems of localization and mapping within the robotic domain were actually coupled and thus, the problem of Simultaneous Localization and Mapping (SLAM) was properly defined. The development of SLAM also made it possible for a robotic system, without any prior knowledge of its environment, to explore the state-space and construct a map using landmarks and its estimated position. This result has obvious implications for the use of robots to explore dangerous areas such as enemy encampments, other planets in the solar system, and underwater environments. The purpose of this research is to simulate the first aspect of SLAM, autonomous localization in an environment with known correspondences.

The Approach

In this research, the Extended Kalman Filter (EKF) was implemented in order to localize an autonomous robot within an environment. The algorithm made use of known correspondences in the environment, thus, saving the problem of extracting features from unknown landmarks for future research. The EKF algorithm was implemented and simulated within the Robot Operating System (ROS) and Stage architectures.  The simulation was initialized with five landmarks, each of a different color and each landmark location was known to the robot. The robot also knew its own state at the start of the simulation. The robot’s motion was modeled after a differential drive, such as a Pioneer or Seekur. Error accumulates in the prediction of the state variables and the covariance matrix until a known landmark is detected, at which point the EKF algorithm can perform an update and resolve state inconsistencies. In this simulation, a color blob finder was utilized to detect landmarks based on their color. Each landmark was assigned a specific color and the robot associated landmark colors with landmark positions. Upon detection of a landmark, the EKF algorithm creates a predicted measurement based on the robot’s predicted position and the map of landmarks. The predicted measurement is compared against the actual measurement to update the robot’s estimated state. The robot in the simulation used a simple motor schema to navigate through the environment while avoiding obstacles. The robot merely moved in a straight line until its laser sensors detected an obstacle within 3 meters, at which point, the robot turned away from the vector pointing from the robot to the obstacle.

Evaluation of Results

X-Position Error

The performance of the EKF localization algorithm was compared against localization only using dead-reckoning. The metric that was used to compare the two localization techniques was the percent error between the estimated position of the robot and the actual position of the robot. Both the dead-reckoning odometry and the EKF localization estimated coordinates were compared against the actual robot coordinates generated by the simulation in the figure to the right. In the figure, the x-axis is the simulation time and the y-axis is the percent error. This plot shows only the percent error for the x-position.

When the percent errors displayed in the figures are compared it is clear that the EKF localization technique predicted state variables that deviated less from the actual state variables than the state variables predicted by dead-reckoning. When comparing the figures it is important to note that the dead-reckoning percent error increased to over -29% while the maximum percent error in EKF was only around -12%. Also, the EKF algorithm usually maintained a percent error near the 0% mark. However, the dead-reckoning technique predicted state variables that oscillated and drifted wildly. A final note about the plots is that the EKF plots show evidence of a periodic waveform. In the EKF plots, both the x and y predicted states begin to deviate from the actual robot position rapidly at the same time. The error in the x and y predicted values then decreased at the same time. This occurred in a periodic fashion. Even though the plots of the dead-reckoning states oscillated, the oscillations in the x and y error plots were not time-correlated.

Coordinated Localization with Multiple Autonomous Underwater Vehicles(PDF)

Towards the end of the course I was asked to write a more substantial research proposal that integrates AI into another discipline.  Naturally, I chose underwater robotics.

Problem Addressed and Its Importance

Remotely operated vehicles (ROV) are used in a number of underwater applications. Human operators use ROVs equipped with video cameras to inspect the hulls of ships and detect faults in underwater cable lines. Unfortunately, ROVs are inherently operated by humans, which occupies an operator’s time while he could be performing other tasks. Two of the main obstacles to a fully automated underwater vehicle are the lack of underwater robotic localization and the lack of reliable communications links. Localization for ground and aerial robotic platforms is often solved with the use of the Global Positioning System (GPS). However, radio frequency (RF) propagation is highly attenuated in water and is often a function of water salinity. Thus, an autonomous underwater vehicle (AUV) could rely upon a form of Simultaneous Localization and Mapping (SLAM) in order to determine its location in a marine environment. There are number of sensors that could be incorporated in the SLAM feedback loop to provide the AUV with data about its environment, such as a high resolution sonar image, video camera, or Doppler velocity logger. Also, using video data to localize underwater can be difficult due to a lack of features in deep water or lack of water clarity. Within the network of AUVs each would be assigned specific roles, such as observing the sea floor for localization or scouting ahead for targets of interest. Thus, the AUVs would only have to maintain localization relative to each other in the network, while only a single AUV would have to maintain global localization. A network of AUVs could also be used in coastal protection to prevent illegal smuggling into the country. Multiple AUVs could also be used to autonomously measure contaminants in the ocean where companies drill for oil. There are a number of challenges involved with implementing a network of AUVs that can maintain localization, but the final product has a number of valuable applications.

Proposed Technical Approach

The network of AUVs will be implemented with three Yellowfins. The Yellowfin is an AUV that was developed at the Georgia Tech Research Institute (GTRI) for the purpose of researching autonomous behaviors. Currently, the Yellowfin is fitted with an INS, acoustic communications module, compass, GPS, depth sensor, and single-board computer with a Linux operating system. In order to improve its localization, the Yellowfin will be retrofitted with a downward-facing DVL. The DVL will be used in concert with the INS to measure the vehicle’s velocity. To improve the AUVs underwater vision, two side-scan sonars will be added to the Yellowfin. The side-scan sonar’s primary function will be feature detection along the seafloor.  Each vehicle will maintain a complete map of the work area and the vehicles will only directly communicate detected landmarks via acoustic communications. In this implementation, whenever a vehicle communicates the observation of a landmark, the data packet will also include a time stamp from which a TOF can be calculated.

Final Comments on CS6601 : Artificial Intelligence

This course, while it was quite a bit of work and writing, gave me a great survey on Artificial Intelligence and at the same time allowed me to experiment with AI techniques in fields that I am really interested. During this course I was exposed to practical aspects such as Prolog, Python, MOOS, ROS, Player/Stage/Gazebo, and Latex, while at the same time, I learned a lot about traditional AI techniques such as search, CSPs, factor graphs, language processing, uncertainty, etc. A great skill that I acquired during this class was the of Latex. I’ve never used Latex before, but after seeing its power and the elegant documents that can be created with it, I’ve decided to try to write all my documentation at GTRI within Latex. Since being exposed to Latex, I’ve progressed from using LyX to writing Latex code directly in TexMaker and finally in Emacs with the Auctex package. This course was definitely great for my exposure to AI techniques as well as a course that helped me to acquire skills that I will require while working towards my PhD in ECE.