Boundary Detection

I am currently finishing work on distributed boundary detection. Similar in spirit to the alpha-shapes of Edelsbruner, it creates a ``skin-tight'' boundary around the network, detecting convex and concave sections. Unlike the centralized definition of the alpha-shape, my work defines the boundary based on the local network geometry, and allows a robot to efficiently compute its boundary status using a distributed algorithm. The pictures below show the results from simulations from two configurations. The algorithm efficiently classifies robots as internal, boundary, or local articulation points. A local articulation point is a robot whose removal disconnects a local region of the graph. These robots are vulnerable points in the network, and can be reinforced by reconfiguring the nearby network to add redundancy to the connectivity. I used boundaries in the directed dispersion algorithm to guide robots into unexplored areas. Other applications for boundaries include updating a database when targets enter or exit the coverage area, generating a virtual fence to keep the robots into one coherent group, or detecting and filling voids in coverage.

Publications

"A Distributed Boundary Detection Algorithm for Multi-Robot Systems" (under review)
   James McLurkin and Erik D. Demaine.

James McLurkin