Project: CIRCLE PLACEMENT PROBLEMS FOR MOBILE ROBOT APPLICATIONS Student Researchers: Joanna Blanding, Xinmei Cai Advisors: Amy Briggs Institution: Middlebury College Many mobile robot applications employ sensors or transmitters embedded in the environment. In some hospitals, for example, robots deliver prescriptions to nurses' stations, navigating the hallways with the aid of tiny radio transmitters installed on the ceilings. Motivated by this example, we are interested in developing strategies for planning the placement of devices (transmitters or sensors) in a robot's environment. The placements should be chosen such that every point in the environment is within range of at least one device and the overall number of such devices is minimal. We assume that each device is effective to a certain fixed distance. Geometrically, this corresponds to a circle of a fixed radius at each device placement. Our problem then, is to cover the environment with overlapping circles, each circle enclosing the area covered by one device. Our goal in this project will be to design, implement, and experiment with algorithms for covering a convex polygon with a minimal number of fixed-radius circles. Related problems to be explored include: the extension to simple polygons, circles of different radii, and the case when placements are restricted to the boundary of the polygon.