Luther Tychonievich and Dr. Robert P. Burton, Computer Science
Hypertime, or nT research, is a relatively unexplored field. Like its sister field of hyperspace, or nD research, hypertime extends the universe by considering additional dimensions. Where hyperspace extends the universe by considering four or more spatial dimensions, hypertime considers universes characterized by two or more time dimensions. An intuitive understanding of hypertime may be gained by imagining the time line replaced by a time plane in a digital movie player, as illustrated in Figure 1.
While the primary challenge of hyperspace research is visualization, nT research is faced with the more fundamental problem of simulating what hypertime environments are like. In unpublished research performed by the author last year, the first working hypertime simulation was created, using elastic particle collisions as the simulation model. The research discussed in this paper focuses not on physics but on artificial intelligence (AI) in a hypertemporal setting. While an understanding of hypertemporal physics is valuable, the lessons learned in designing choice-making agents sheds more light on the various qualities of nT environments.
The primary difficulty facing hypertime AI is that standard concepts of discrete iteration, potential fields, and the like are unstable in two or higher dimensions [1]. I therefore selected an AI model using the geometric obstacle avoidance technique independently proposed by two different groups in the late 80s and early 90s [2, 3]. The core concept in this algorithm is to consider the velocity of the obstacles in addition to their positions to discover velocities that will result in a collision (see Figure 2). This is an old and well-established technique used by ocean vessels navigating crowded water, called maneuvering boards, but gains extensive power when a computer can re-compute the legal velocities several times a second.
Because of the geometric nature of this algorithm, it is conceptually easy to extend to higher dimensionalities. Depending on the dimensionality of the time considered, it is enough to add a dimension to the board for every additional time dimension and replace the avoidance cones in the original algorithm with avoidance superquadratics. However, though conceptually simple, this is not computationally easy, being an example of concave optimization, a notoriously hard problem.
The original algorithms were posed with an exhaustive search model. Since they restricted themselves to 2D, n obstacles could contribute at most O(n2) intersection points; one of those had to be the best, so all were checked and the best one used. If extended to arbitrary dimensionality, this quickly becomes an exorbitantly expensive calculation; indeed, initial tests of a naïve hypertime adaptation of their algorithm took anywhere from an hour to a day per second of simulated time, unacceptable for interactive tests.
I first attempted to optimize the search by a number of heuristics, reasoning about whether a given obstacle could contribute to a solution before checking it. While successive iterations of this idea got the computation time down to roughly 5% of the original speed, it was still nowhere near interactive speed. I also attempted a discrete lattice approach, which ran at interactive speeds, but was unacceptably inaccurate in practice.
My final solution was a specialized form of stochastic optimization tailored to the particular features of this problem. I first observed that the best possible velocity had to fall somewhere within the maximum velocity hypersphere. The algorithm thus picks one of these points at random and checks it against each obstacle to see if it is a legal velocity. If not, it picks another random point and repeats. Once a legal velocity is found, the region of possible best velocities shrinks to the velocities better than the known velocity and less than the maximum velocity. By randomly selecting from only this area, rapid convergence results in the average case, usually within a few hundred test points, sufficient for interactive real-time simulations of several simultaneous hypertime agents.
However, much better performance is possible using the fact that ideal velocities usually don’t change much from one moment to another. By focusing half the search effort in the region immediately surrounding the last known ideal velocity, reasonable convergence is seen in as few as twenty iterations. Using this tuned stochastic method, I created a simple hypertime AI test suite that can simulate over a hundred real-time agents at the same time on a standard desktop PC.
Although much work is still needed to discover what hypertime AI means for the nature and structure of hypertime, I have created such an algorthim, the first step in this exciting new field of research.
References
- Tegmark, M. “On the Dimensionality of Spacetime” Classical and Quantum Gravity 1997. Vol. 14 pp. L69–L75
- Tychonievich, L., Zaret, D., Mantegna, J., Evans, R., Muehle, E., and Martin, S. “A Maneuvering-Board Approach to Path Planning with Moving Obstacles” Proc. 11th International Joint Conference on Artificial Intelligence, 1989. pp. 1017–1021
- Fiorini, P., and Shiller, Z., “Motion Planning in Dynamic Environments Using the Relative Velocity Paradigm,” IEEE Conf. on Robotics and Automation, Atlanta, GA, May 1993. Vol. 1, pp. 560–565.