Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Home Page for Stephen Matysik | Parasol Laboratory

Picture Stephen Matysik
Algorithms & Applications Group

Parasol Laboratory url: http://parasol.tamu.edu/~smatysik/
Department of Computer Science and Engineering email:
Texas A&M University office: 407 HRBB
College Station, TX 77843-3112 tel: (979) 458-4850
USA fax: (979) 458-0718

Background:      Graduated Lower Moreland High School in 2007
                            Currently attends Vassar College as a rising sophmore
                            Major: Undecided

Research Mentor: Jennifer Walter
                             Vassar College
                             Computer Science Department
                             Distributed Algorithms, specifically for mobile ad hoc networks and for
                                      modular, reconfigurable robotic systems.
                             url: http://www.cs.vassar.edu/~walter/

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.  
Weekly updates:
Week 3:
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.
Week 4
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.
Week 5
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.