Graduated Lower Moreland High School in 2007
Currently attends Vassar College as a rising sophmore
Research Mentor: Jennifer Walter
Computer Science Department
Distributed Algorithms, specifically for mobile ad hoc networks and for
modular, reconfigurable robotic systems.
Research Topic: Motion planning for metamorphic hexagonal robots,
specifically filling a goal shape with multiple obstacles
Research Goals: Find an algorithm to fill a goal containing multiple obstacles
by creating a large pocket around the obstacles, then bridge
the obstacles to the pocket, fill the pocket, and then fill the
remaining goal cells. First, I will do this by first filling the perimeter
of the goal shape, effectively creating a large pocket around the
obstacles, then proceed to bridge the obstacles to the perimeter and
fill the goal shape. Second, I will implement a convex hull algorithm
to form close perimeter around the obstacles, then fill the remaining
goal shape. Once this is completed, the two methods can be compared
to determine which is more efficient.
Dr. Walter and I have successfully written an algorithm to find and fill the cells on the perimeter of any goal configuration. We found errors in the way in which the old pocket filling algorithm determines the order the pocket cells are filled. We corrected these errors and can now successfully fill any goal configuration with no obstacles by filling the perimeter cells first, then filling the pocket created by the perimeter, and finally filling any unfilled cells outside the perimeter.
This week we discussed our plan to fill goal configurations that contain one or more obstacle cells. The plan is first create a pocket around the goal and mark the neighbor cells of any obstacles in the configuration. Then we label the inside of the pocket and find the next cell to be filled with the techniques we used to fill an obstacle-free pocket. Next, we check if the cell we are about to add has a neighbor cell that is a neighbor of an obstacle as well. If it is, we fill that neighbor cell, effectively bridging the obstacle to the perimeter. Then we add the obstacle and the bridge to the perimeter, and relabel the perimeter. We repeat this until the goal configuration is filled. Update-- We have successfully implemented this algorithm and after testing it appears to be quite robust. We will do more testing.
The algorithm we implemented seems to be very effective. We started to study how we could implement a convex hull algorithm to solve this problem in a different fashion, but it seems that it would be inefficient and overly complex. So, we have decided for now to write a paper on the algorithm we developed. Recently we have reexamined our code and found parts that seem to have the potential to be broken. We will fix these parts and continue with the paper.
For more information, please go to my REU blog.
Parasol Home | Research | People | General info | Seminars | Resources
Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112
firstname.lastname@example.org Phone 979.458.0722 Fax 979.458.0718
Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU
Web Accessibility Policy and Law - Web Accessibility and Usability Standards - Contact Webmaster