| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Home Page for Stephen Matysik | Parasol Laboratory

Stephen Matysik
Undergraduate
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.

 Parasol Home | Research | People | General info | Seminars | Resources   Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112  parasol-admin@cse.tamu.edu      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