Home Page for Stephen Matysik | Parasol Laboratory
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.
