TR-04-05: Calculating the Meeting Point of Scattered Robots on Weighted Terrain Surfaces

Abstract

In this paper we discuss the problem of determining a meeting point of a set of scattered robots R = {r1, r2, …, rs} in a weighted terrain P which has n > s triangular faces. Our algorithmic approach is to produce a discretization of P by producing a graph G = {VG, EG} which lies on the surface of P. For a chosen vertex p’ in VG, we define || �(ri, p’) || as the minimum weight cost of traveling from ri to p’. We show thatmin{p’ in VG}{max{1<= i <= s} {|| �(ri, p’) ||}} <= min{p* in P}{max{1 <= i <= s}{|| �(ri, p*) ||}} + W|L|

where L is the longest edge of P, W is the maximum cost weight of a face of P, and p* is the optimal solution. Our algorithm requires O(snm log(snm) + snm2) time to run, where m = n in the Euclidean metric and m = n2 in the weighted metric. However, we show through experimentation that only a constant value of m is required (e.g., m = 8) in order to produce very accurate solutions (< 1% error). Hence, for typical terrain data, the expected running time of our algorithm is O(sn log(sn)). Also, as part of our experiments we show that by using geometrical subsets (i.e., 2D/3D convex hulls, 2D/3D bounding boxes and random selection) of the robots we can improve the running time for finding p’, with minimal or no additional accuracy error when comparing p’ to p*.