Skip to content

Departmental Seminar: David Kirkpatrick

Thursday, 23rd November 2017 1:00 pm
Where: EITC E2-304

Title: Minimizing uncertainty in the proximity of moving agents

Speaker: David Kirkpatrick, University of British Columbia

Departmental Seminar: David Kirkpatrick


Search problems are conventionally understood in terms of minimizing uncertainty in the location of one or more agents (perhaps moving in an adversarial fashion), using some form of spatial queries. We consider, and encourage further consideration of, a natural  modification in which the goal is to reduce uncertainty, attributable to unmonitored motion,  concerning the proximity, rather than absolute location, of a collection of moving agents.

For example, imagine a collection of point agents moving in a graph (or some subset of one-, or higher,dimensional Euclidean space) each with some (known, but possibly different) upper bound on their speed.  If we know, by means of an individual location query, the precise location of an individual agent at a particular time, then its location, until the time that it is next queried, lies in  a steadily-expanding region of uncertainty. Motivated by the fact that resource demands are often commensurate with congestion (e.g. bandwidth allocation), we consider the problem of minimizing measures of potential congestion—maximum local congestion, over all agent configurations consistent with the current uncertainty of the collection—using individual queries that are restricted to one query per unit of time.

Our focus to date has been on the degree of the uncertainty regions (defined as the maximum, over all agents a, of the number of uncertainty regions that intersect the uncertainty region of a), a natural measure of worst-case congestion, for point agents moving continuously in one-, or higher,dimensional Euclidean space. The goal is to minimize this degree continuously. Competitive query strategies are described in terms of a notion of intrinsic degree (the minimum degree achievable by any query strategy, even one that knows the trajectories of all agents). Only partially studied to date are analogous questions for agents moving in a graph.

(Based on joint work with Daniel Busto, and Will Evans)

Complete Seminar List
© 2011 University of Manitoba Department of Computer Science
Back to top