In this paper, we formalize the problem of partial barrier coverage, that is, the problem of using robot sensors (guards) to minimize the probability of undetected intrusion in a particular region by an intruder. We use ideas from noncooperative game theory together with previous results from complete barrier coverage - the problem of completely preventing undetected intrusion - to develop new methods that solve this problem for the specific case of bounded-range line-of-sight sensors in a two-dimensional polygonally-bounded region. Our solution constructs equilibrium strategies for the intruder and guards, and calculates the level of partial coverage.

In this paper, we formalize the problem of barrier coverage, that is, the problem of preventing undetected intrusion in a particular region using robot sensors. We solve the problem of finding the minimum-length barrier in the case of variable bounded-range line-of-sight sensors in a two-dimensional polygonally-bounded region. We do this by building a graph of candidate barriers that could potentially be in the minimum barrier. The dual of this graph shows the connectivity of the free space. We thus reduce the problem to the network flows maximum-flow/minimum-cut problem.

In many multirobot applications, the specific assignment of goal configurations to robots is less important than the overall behavior of the robot formation. In such cases, it is convenient to define a permutation-invariant multirobot formation as a set of robot configurations, without assigning specific configurations to specific robots. For the case of robots that translate in the plane, we can represent such a formation by the coefficients of a complex polynomial whose roots represent the robot configurations. Since these coefficients are invariant with respect to permutation of the roots of the polynomial, they provide an effective representation for permutation-invariant formations. In this paper, we extend this idea to build a full representation of a permutation-invariant formation space. We describe the properties of the representation, and show how it can be used to construct collision-free paths for permutation-invariant formations

In this paper we demonstrate path planning for our formation space that represents permutation-invariant multi-robot formations. Earlier methods generally pre-assign roles for each individual robot, rely on local planning and behaviors to build emergent behaviors, or give robots implicit constraints to meet. Our method first directly plans the formation as a set, and only afterwards determines which robot takes which role. To build our representation of this formation space, we make use of a property of complex polynomials: they are unchanged by permutations of their roots. Thus we build a characteristic polynomial whose roots are the robot locations, and use its coefficients as a representation of the formation. Mappings between work spaces and formation spaces amount to building and solving polynomials. In this paper, we construct an efficient obstacle collision detector, and use it in a local planner. From this we construct a basic roadmap planner. We thus demonstrate that our polynomial based representation can be used for effective permutation invariant formation planning.

In this paper we consider the problem of maintaining surveillance of a moving the target by a nonholonomic mobile observer. The observer's goal is to maintain visibility of the target from a predefined, fixed distance, l. The target escapes if (a) it moves behind an obstacle to occlude the observer's view, (b) it causes the observer to collide with an obstacle, or (c) it exploits the nonholonomic constraints on the observer motion to increase its distance from the observer beyond the surveillance distance l. We deal specifically with the situation in which the only constraint on the target's velocity is a bound on speed (i.e., there are no nonholonomic constraints on the target's motion), and the observer is a nonholonomic, differential drive system having bounded speed. We develop the system model, from which we derive a lower bound for the required observer speed. Finally, we consider the effect of obstacles on the observer's ability to successfully track the target.

In this paper we describe a new representation for a configuration space for formations of robots that translate in the plane. What makes this representation unique is that it is permutation-invariant, so the relabeling of robots does not affect the configuration. Earlier methods generally either pre-assign roles for each individual robot, or rely on local planning and behaviors to build emergent behaviors. Our method first plans the formation as a set, and only afterwards determines which robot takes which role. To build our representation of this formation space, we make use of a property of complex polynomials: they are unchanged by permutations of their roots. Thus we build a characteristic polynomial whose roots are the robot locations, and use its coefficients as a representation. Mappings between work spaces and formation spaces amount to building and solving polynomials. In this paper we also perform basic path planning on this new representation, and show some practical and theoretical properties. We show that the paths generated are invariant-relative to their endpoints - with respect to linear coordinate transforms, and in most cases produce reasonable, if not linear, paths from start to finish.