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 = {V G,E G} which lies on the surface of P. For a chosen vertex p ′ ∈ V G, we define ‖Π(ri,p ′)‖ as the minimum weight cost of traveling from ri to p ′. We show that minp ′ ∈V G{max1≤i≤s{‖Π(ri,p ′)‖}} ≤ minp∗∈P{max1≤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(snmlog(snm)+snm 2) 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(snlog(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 ∗. 1