DIMACS
DIMACS REU 2017

General Information

me
Student: Edgar Jaramillo Rodriguez
Office: 434 CoRE Building
School: University of California Berkeley
E-mail: ejaramillo@berkeley.edu
Project: Toward the Design Optimization of Multi-Robot Systems

Project Description

My project focuses on improving solutions to the Multirobot Path Planning problem, a formulation of which can be found here. My goals for the summer are to work on improving the computing times of existing algorithms and heuristic approaches. Additionally, I am interested in developing a simulator that will allow us to test solutions in environments with large numbers of densely distributed robots. Finally, I might also look to real life applications of this problem and design environments that reflect the relevant variables.

Weekly Log

Week 1 (5/29):
This week, I focused on conducting a literature review of the existing material surrounding this problem. In particular, I studied Dr. Yu's paper, "Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics" (full reference below). I also met with Shuai Han, one of Dr. Yu's graduate students, to see a demonstration of the swarm robotic platform at their lab. After that, I began reviewing the code behind their system, trying to get a basic, general understanding. Finally, I am also preparing a short presentation describing my project and goals to be given on June 5th, 2017.
Week 2 (6/5):
Because my mentor was away, I spent this week building a simulator to test the effectiveness of existing MPP-algorithms and heuristics. My simulator can now model the movement of hundreds of differential drive robots moving on the plane. In the near future I hope to add support for other drive models. I did this coding in Python.
Weeks 3 and 4 (6/12, 6/19):
I have grouped these weeks together since my work was basically the same from one to the next. Upon the return of my mentor, Dr. Yu, we have begun our research in earnest. We have decided to work on developing a complete algorithm to provide a solution to the MPP problem on a continuous space. That is, rather than working with robots located on discrete nodes and moving along edges, robots will be allowed to move freely in the plane on continuous time. This problem is therefore much more relevant to real life robotics applications. In particular, we would like our algorithm to have some guarantee of optimality (i.e. it is bounded by some constant multiple of the optimal solution) and to use a limited region of the plane since this problem is trivial if we are allowed to send robots to plus or minus infinity and solve them one by one. Our initial idea for this algorithm is to use what we know of the discrete version, particularly the very good algorithms we have for grids, and reduce the continuous problem into one which we already know how to solve. Thus, the challenge during these weeks was to develop a good map from robots distributed on a continuous space, potentially packed very tightly, onto a grid. We believe we have done so using new techniques and some of Dr. Yu's prior work.
Weeks 5 and 6 (6/26, 7/3):
I have also grouped these weeks together since my work was basically the same from one to the next. During this time I primarily worked to rigorously prove some key aspects of our algorithm. Without going into too much detail, the main problem I worked on was proving that our algorithm for mapping robots from a continuous space onto a grid was complete and efficient. By complete, I mean proving that our algorithm was vialbe (would not results in any collisions) no matter what the initial configuration of robots is. By efficient I mean guaranteeing that the map could be executed in some polynomial time. We in fact did better than this; our map can executed in constant time. Han and I also began compiling our work and proofs in a shared LaTeX document which we hope to turn into the first draft of our paper by the end of the summer.

Presentations

Additional Information