A large portion of my Spring 2021 semester was spent working on various AMR tasks and projects, and despite the enormous workload, this was a fantastic class that drew my interest towards autonomy and the algorithms behind robotics.
The class primarily involved sensing, localization, mapping, path planning, motion planning, obstacle and collision avoidance, and multi-robot control. Each algorithm was explained during lecture, and then we were tasked to implement these (effectively from scratch) in MATLAB. During lab, we used the iRobot Create platform to run our code on physical robots, which required us to deal with imperfect sensors and delays.
At the end of the year, we divided into teams for a final competition. For this, the robot was placed at an unknown position on an unknown map, and we had to localize and plan our route around the map to maximize the points collected by visting as many waypoints as possible within 5 minutes.
Key algorithms used:
- Kalman Filter
- Extended Kalman Filter
- Particle Filter
- Grid Localization
- Potential Functions
- Navigation Functions
- Dijkstra’s Algorithm
- Delaunay Triangulation / Cell Decomposition
- Occupancy Grid / Mapping
- Roadmaps / Probabilistic Roadmaps (PRM)
- Rapidly-Exploring Random Trees (RRT)
- Feedback Linearization
- Dead Reckoning
- Reference frame conversion
Physical robots (roombas) used during in-lab testing.
Selected Algorithm Figures
Potential Functions
Rectangular objects in the physical world were represented by spherical potential functions in the digital world, with the robot following the inverse gradient towards the goal at a global minimium.
Rapidly-Exploring Random Trees (RRT)
RRTs were implemented as another means of path planning through a map where the start and goal points are known, and where we can check whether a candidate node (and its connection to the tree) exist within the free space. Random sampling of the search space allows for this tree to expand across the map until a connection can be made with the goal.
Dijkstra’s Algorithm (and Delaunay Triangulations)
Here, a roadmap is generated via the center points of a Delaunay triangulation of the workspace. A desired start and end point is connected to the center points of the decomposed cells in the workspace, and Dijkstra’s algorithm is applied to find the shortest path through the roadmap.
Grid Localization
Grid localiaztion was achieved using an inverse sensor model based around the bump sensor and depth measurements. Here, various grid resolutions and trajectory lengths are compared to see how well the workspace is represented.
Final Competition
Flowchart
A general summary of my team’s strategy for the final competition.
Particle Filter and Noise Data
A major strength of our code for the final competition was how well the particle filter handled noise in the depth measurement data. Even with large standard deviations in the measurements, the robot was still able to traverse the map due to our averaging and filtering method.
Roadmap
We built a robust roadmap using a combination of grid-based and random sampling and k-nearest-neighbor connection methods. This created a roadmap that was guaranteed to cover the workspace even with an unknown map, with a low computation time.