15-494 Cognitive Robotics 2008 Final Project

Sheep Herding

Christopher Solidum


Goals Boundary Detection Manipulation Results Future Work


The first major part of my project was finding the boundaries of the sheep’s pen and determining what’s inside it.

There were several different methods available to detect the boundaries of the sheep’s pen.


Method 1:  Use the MapBuilder to find all the pink lines in the area, then use the PolygonData constructor to build the boundaries



                        -  Fast

                        -  Simple to compute

                        -  Relatively long range


-          Hard to order the lines to create the correct boundary


Method 2: Use the MapBuilder to find all the pink lines in the area, then form the boundary based on the intersections of the lines



                        -  Relatively long range


                        -Complicated to find which lines are supposed to intersect with each other



Current Method: Use MapBuilder to find all the pink lines in the area, then construct boundaries by summing together the halfplanes of all the lines



-          Relatively simple

-          Robust against noise


-          Requires us to significantly reduce the resolution of the local sketch space

-          Only valid within a certain range


The Algorithm:

Use the MapBuilder to find pink lines

For Each Line

            If the line is Vertical

                        If more lines are below it than above

                                    Render bottom half plane


                                    Render Top half plane


                        If more lines are to the right of it than to the left

                                    Render right half plane


                                    Render left half plane

Sum together all the renderings to create the inside of the sheep pen

Use PolygonData::convexHull to create the bounding polygon







Detecting Inside:

            In order to detect if the an easter egg is out of place, the AIBO performs the PolygonData::isInside function using the bounding polygon and the center of the esater egg. It then performs a color check to see if its out of place.


Easter egg Inside:



            Given that there are no easter eggs (sheep) out of place, the AIBO will patrol around the boundary. This is done by finding the second closest line (based on line center) and moves to that point using the pilot. The AIBO repeats this until it finds an easter egg out of place. Videos of the AIBO Patroling can be seen on the results page.