During Summer 2018 MEGL ran a small program with 7 participants. There was one research group, [name]. The group engaged in experimental exploration involving faculty, graduate students and undergraduates. The team met weekly to conduct experiments generating data, to make conjectures from data, and to work on theory resulting from conjectures.
The rapidly-exploring random tree (RRT) algorithm is a quick-working tool often used for solving path-finding problems, even in high-dimensional spaces with obstacles and differential constraints. Given a real metric space, a method of traveling between points, and a starting location, an RRT algorithm will explore the space through branching tree of paths to travel around the space. Given enough time, a variation of RRT called RRT* will grow a branch with the optimal path in the space to any goal area.
The simultaneous motion of N cars moving around a parking garage can be decently modeled by paths in a 3N-dimensional metric space, where each car is given two position (where the car is located) coordinates and one orientation (which direction the car is facing) coordinate. In this project we wrote an RRT* program utilizing this model that finds an optimal and collision-free simultaneous paths of multiple cars traveling across a garage with polygonal obstacles. This is one of the first implementations of the RRT algorithm of its kind, and as the age of self-driving cars draws nearer, algorithms like this must be studied so that valet parking garages can coordinate cars in and out of them as quickly and efficiently as possible (without colliding with each other).
At the same time, to fully visualize and confirm the results of our code in a real-life application, we aimed to simulate our results with mobile robots moving around an obstacle course. We wrote code programs to drive multiple robots called Flockbots along our RRT* code’s given paths simultaneously, all the while watching them with a camera following the Flockbots’ AR tags so we can correct any errors in their paths.