Open Collections

Scheduling queries to moving entities to certify many are distant from a region

University of British Columbia

Let e1, e2, . . . , en be a set of entities moving with bounded speed in d-dimensional space. At each time step, we can choose one entity to query to obtain its actual location. Our goal is to establish via these queries that many of the entities could not be at a fixed point called a beacon. By failing to query an entity, the set of its potential locations, called its uncertainty region, grows over time. We want to query to keep the number of uncertainty regions that do not overlap the beacon (i.e., the number of entities away from the beacon) as large as possible. Of course, if many entities are near the beacon, we cannot avoid high overlap, but neither can any query schedule. We describe query schedules that establish that the number of entities away from the beacon is a constant fraction of the maximum number that can be shown to be away from the beacon in the case where each entity is static that is, every query reveals that the entity has not moved. In the general setting we show additive upper and lower bounds on what can be attained by a query schedule.

Text

2020-08-20

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/75616

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/