We consider the problem of localizing a robot in a known environment modeled by a simple polygon P. We assume that the robot has a map of P but is placed at an unknown location inside P. From its initial location, the robot sees a set of points called the visibility polygon V of its location. In general, sensing at a single point will not suffice to uniquely localize the robot, since the set H of points in P with visibility polygon V may have more than one element. Hence, the robot must move around and use range sensing and a compass to determine its position (i.e., localize itself). We seek a strategy that minimizes the distance the robot travels to determine its exact location. We show that the problem of localizing a robot with minimum travel is NP-hard. We then give a polynomial time approximation scheme that causes the robot to travel a distance of at most (k - 1)d, where k = |H|, which is no greater than the number of reflex vertices of P, and d is the length of a minimum length tour that would allow the robot to verify its true initial location by sensing. We also show that this bound is the best possible.

We consider the problem of verifying a simple polygon in the plane using “test points”. A test point is a geometric probe that takes as input a point in Euclidean space, and returns “+” if the point is inside the object being probed or “−” if it is outside. A verification procedure takes as input a description of a target object, including its location and orientation, and it produces a set of test points that are used to verify whether a test object matches the description. We give a procedure for verifying an n-sided, non-degenerate, simple target polygon using 5n test points. This testing strategy works even if the test polygon has n + 1 vertices, and we show a lower bound of 3n + 1 test points for this case. We also give algorithms using O(n) test points for simple polygons that may be degenerate and for test polygons that may have up to n + 2 vertices. All of these algorithms work for polygons with holes. We also discuss extensions of our results to higher dimensions.

The problem of localization, i.e. of a robot finding its position on a map, is an important task for autonomous mobile robots. It has applications in numerous areas of robotics ranging from aerial photography to autonomous vehicle exploration. In this paper we present a new strategy for a robot to find its position on a map where the map is represented as a geometric tree. Our strategy exploits to a high degree the self-similarities that may occur in the environment. We use the framework of competitive analysis to analyze the performance of our strategy. In particular, we show that the distance traveled by the robot is at most O(pn) times longer than the shortest possible route to localize the robot, where n is the number of vertices of the tree. This is a significant improvement over the best known previous bound of O(n2=3). Moreover, since there is a lower bound of \\Omega (pn), our strategy is optimal up to a constant factor. Using the same approach we can also show that the problem of searching for a target in a geometric tree, where the robot is given a map of the tree and the location of the target but does not know its own position, can be solved by a strategy with a competitive ratio of O(pn), which is again optimal up to a constant factor.

A testing algorithm takes a model and produces a set of points that can be used to test whether or not an unknown object is sufficiently similar to the model. A testing algorithm performs a complementary task to that performed by a learning algorithm, which takes a set of examples and builds a model that succinctly describes them. Testing can also be viewed as a type of geometric probing that uses point probes (i.e. test points) to verify that an unknown geometric object is similar to a given model. In this paper we examine the problem of verifying orthogonal shapes using test points. In particular, we give testing algorithms for sets of disjoint rectangles in two and higher dimensions and for general orthogonal shapes in 2-D and 3-D. This work is a first step towards developing efficient testing algorithms for objects with more general shapes, including those with non-orthogonal and curved surfaces.

We examine the complexity of testing different program constructs by defining a measure called VCP-dimension and applying it to classes of programs, where all programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine approximate correctness, so it gives insight into the difficulty of testing a program construct represented by a program class. We investigate the VCP-dimension of straight line code, if-then-else statements and for loops, and we compare the VCP-dimension of different combinations of constructs.>

A model for approximate testing of concepts, which relates to the PAC model of learning, has been developed. In this model an approximate testing algorithm produces a finite set of examples that distinguishes one concept from others that differ from it by more than a given error bound. This model corresponds closely to the helpful teacher learning model. In this paper we examine properties of a concept class that make it testable or untestable. We define a new measure that is a dual to the VC-dimension, called the testing dimension of a concept class, and show how it yields untestability results for certain concept classes.