Real-Time Kinetic Algorithms

Patchrawat Uthaisombut
Department of Computer Science, University of Pittsburgh
, www.cs.pitt.edu/~utp

What's a kinetic problem?

In a kinetic problem, there is a system that contains real-valued parameters and a function on these parameters.  The parameters of the system change continuously over time.  As the parameters change, the value of the function changes.  In many cases, the value of the function at a particular time can be described by a simpler combinatorial description (called configuration) together with the value of the input parameters at that time.  The goal is to compute the value (or a close approximation of the value) of the function over time.  The challenge is to find the most efficient way to do this by exploiting fact that the input parameters change in a continuous manner but the configuration only changes at discrete times.

Example of kinetic problem

An example of a kinetic problem is a system of points on the plane that move continuously over time, and the objective is to maintain a minimum spanning tree (MST) of these points over time.  Here the configuration at a particular time is the set of edges (or point pairs) of an MST at that time.  The value of the function at that time is the total weight of the edges in the MST (where the weight of an edge is the distance between the two end points of the edge).  Observe that the set of edges only changes at discrete time, but edge weights change continuously (because points move continuously).

Our New Model: the Real-Time Kinetic Model

We introduce the real-time kinetic (RK) model for studying kinetic problems.  This model has the following features.  We assume that the speed of any object at any time is no greater than a certain maximum speed S_max.  An object can move on an arbitrary trajectory.  Furthermore, the algorithm learns the position of the objects in an online fashion, that is, the algorithm does not know and cannot predict with certainty the position of an object in the future. The algorithm must maintain the configuration in real time, that is, it performs computation at the same time that the parameters of the system are changing.  Generally the optimal configuration cannot be maintained at all time under reasonable assumptions. Thus, we settle for an approximate configuration.  In such cases, we are interested in the quality of the value of the configuration, i.e. how close it is to the value of the optimal configuration.

Related Work by Others

Kinetic problems have been studies under different assumptions.

• Known trajectory: If the complete trajectory of each object is known in advance, it is possible to efficiently compute the combinatorially distinct configurations that the objects will be in. A framework for such an analysis is given by Atallah [Atallah85].
   
• Trajectory in the near future is known:  Kinetic data structures (KDS) was introduced by Basch, Guibas, and Hershberger [BGH99].  In the KDS model, it is still assumed that trajectories of objects are known.  However, trajectories can be updated over time in an online fashion, that is, the algorithm does not know when trajectories will change.  In the KDS model, two (among four) of the goals are to minimize the amount of computation per event to maintain the certificates (called responsiveness) and the ratio of the number of internal and external events (called efficiency).
   
• Comparisons: Algorithms in the KDS model are not meant to run in real time. Therefore, the issue on degeneracy is left untouched. If many events occur in a short period of time, there is no guarantee on the timeliness or the quality of the solution. The KDS model is appropriate for non-real-time applications where objects move under some known law, but some events may cause the trajectory of objects to change. An example is the simulation of billiard balls colliding each other. In the RK model, algorithms run in real time and deal with degeneracy directly. The RK model is appropriate for real-time monitoring of real physical systems that evolve in an unknown or unpredictable way. Examples are tracking an autonomous moving object in a sensor network and maintaining an MST of nodes in a mobile ad hoc network.

Project Goals

• To develop real-time kinetic algorithms for specific fundamental problems and practical problems in computer science.
• To identify the relationship between problems and techniques in the RK model and existing models, in particular, the static model, the dynamic model, and the KDS model.
• To develop new techniques that can be applied to a wide range of problems in the RK model.

Problems

• minimum spanning tree, shortest path
• closest pair
• triangulation
• covering by unit squares or disks
• k-clustering
• convex hull
• minimum bounding rectangle
• etc.

References

• [Atallah85] M.J. Atallah.  Some dynamic computational geometry problems, Computers and Mathematics with Applications, 11:1171-1181,1985.
   
• [BGH99] Julien Basch, LeonidasJ. Guibas, and John Hershberger.  Data structures for mobile data.  Journal of Algorithms, 31(1):1-28, 1999.
   

Our Results

• Real-Time Kinetic Algorithms, Patchrawat Uthaisombut.  Technical Report, Department of Computer Science, University of Pittsburgh, 2005.  Submitted for publication. [ps|pdf].

Presentation

• Real-Time Kinetic Algorithms, Patchrawat Uthaisombut.  15th Annual Fall Workshop on Computational Geometry and Visualization (FWCG 2005), University of Pennsylvania, November 18-19, 2005.   Abstract. [ps|pdf].

Address for this page is www.cs.pitt.edu/~utp/kinetic.
Back to Patchrawat "Patch" Uthaisombut's page: www.cs.pitt.edu/~utp.