We are currently finishing work on distributed boundary detection. Similar in spirit to the alpha-shapes of
alpha-shapes of Edelsbrunner, 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.
Current researchers: James McLurkin
Project Status: Active