Warped Hypertime Representations for Long-term Autonomy of Mobile Robots

In plain words

A robot that works in a building for months sees the same things happen at the same times of day, week after week. A plain model of "what is usually true here" ignores the clock. A model that treats time as a straight line also struggles, because 23:59 and 00:01 look far apart even though nothing changes at midnight.

The paper's trick is to wrap time around circles. Each repeating pattern (for example a one-day cycle) gets its own circle, and every measurement is placed on that circle according to its time of day. Measurements taken at the same time of the day then land close together, and Monday morning looks like Tuesday morning. The robot first finds which cycles matter, adds the circular coordinates to its location data, and then fits an ordinary statistical model to the result. Asking the model about a place and a time gives a full probability distribution, not just one number. This works for true or false states, such as whether a door is open, and for continuous values, such as how fast the robot should drive.

TL;DR

Time is projected onto a sequence of circles, one per periodicity found in the data, and the extended vectors are clustered with a Gaussian mixture. The model predicts a full distribution p(a | x, t) for any place and time. The paper reports better predictions than static, histogram and FreMEn baselines on four robot datasets, but gives the numbers only in figures fig. 2–fig. 5.

Problem

Robots that work in human-populated spaces need to predict environment states that change with routines: door states, landmark visibility for localisation, robot speed, and people counts §1 §3.1. FreMEn models each binary state as a sum of sinusoids over time §2 §3.1, but it was built for independent binary states and models each state separately. It cannot give a joint distribution over a continuous value, space and time §1 §2.

The method assumes the observed phenomena are repeated with a stable, approximately periodic pattern §1 §3.2. It also assumes that data taken at different times is comparable once projected onto the circles §3.2. The authors note that data was collected irregularly, with long gaps, and that the robot's sampling pattern shapes the learned distribution §4.3 §5.

Method

Notation. Measurements are tuples (a_i, x_i, t_i), i = 1..l: the value a_i (for example a number of people, a visibility, or a velocity), the location x_i, and the time t_i §3.3. The model is a density p(a, x, t) over value, location and time §3.3.

Overview. The method has five stages: initialisation, spatio-temporal clustering, model error estimation, identification of periodicities, and hypertime extension. Stages 2 to 4 repeat while the error keeps falling §3.3. The loop is shown in the pseudocode below.

Step I, initialisation §3.4. Start with h = 0 known periodicities, so each vector holds the value and the location, (a_i, x_i). The count h is the number of periodicities added so far.

Step II, spatio-temporal clustering §3.5. Model the density as a weighted sum of n multivariate Gaussians over the extended vectors eq. 2. The time part of each vector is the list of cosine and sine pairs, one pair for each periodicity found so far eq. 2.

Step III, model error §3.6. Because projecting time onto circles changes the scale of the density, a scale factor γ is chosen so that the model's average value over the training samples matches the measured average eq. 3. For each training sample, compute the mean μ_i of a under the model eq. 4, the residual μ_i − a_i eq. 5, and the error E_h as the sum of squared residuals eq. 6. Keep the current model when E_h is smaller than the previous E_(h−1), and stop when it is not §3.6. To predict, fix x and t, evaluate the density on a grid of candidate values of a, and normalise so the probabilities sum to one §3.6.

Steps IV and V, periodicity and extension §3.7. Find the period that best explains the error. The paper uses a FreMEn-style spectral scan over candidate periods, applied to the mean-removed error series eq. 7. Then add a cosine and a sine of t/T for the chosen period to every vector eq. 1. The result has 2 more dimensions for every periodicity, so after h periodicities the vector has 2h extra dimensions §3.7 eq. 1.

Clustering choices §3.8. Two clustering methods are used.

• HyT-EM: Expectation Maximisation with a fixed number of clusters k. The paper uses an OpenCV implementation, checks the covariance eigenvalues, and restarts with new initial cluster positions when the fit is unstable §3.8.
• HyT-KM: starts from k-means centres, uses a mixture of cosine distance for the time dimensions and Euclidean distance for the others, then runs EM with the cosine distance for the time dimensions §3.8. It chooses the number of clusters itself: it starts at one cluster and adds one when a spectral sum over the error changes in its favour §3.8 eq. 8.

Equations, in the order they appear in the paper's source §3.4–§3.8:

{}^{h+1}\mathbf{x}_i \leftarrow ({}^{h}\mathbf{x}_i,\ \cos(2\pi t_i/T_{h+1}),\ \sin(2\pi t_i/T_{h+1})) eq. 1

p(a,\mathbf{x},t) = \gamma \sum_{j=1}^{n} w_j\, u_j(a,\mathbf{x},{}^{h}\mathbf{t}) eq. 2

with {}^{h}\mathbf{t} = (\cos(2\pi t/T_1), \sin(2\pi t/T_1), \ldots, \cos(2\pi t/T_h), \sin(2\pi t/T_h)) §3.5.

\gamma = \frac{\sum_{i=1}^{l} a_i}{\sum_{i=1}^{l} a_i \sum_{j=1}^{n} w_j\, u_j(a_i,\mathbf{x}_i,{}^{h}\mathbf{t}_i)} eq. 3

\mu_i = \int a\, p(a,\mathbf{x}_i,t_i)\, da eq. 4

{}^{h}\epsilon(t_i) = \mu_i - a_i eq. 5

E_h = \sum_{i=1}^{l} \left({}^{h}\epsilon(t_i)\right)^2 = \sum_{i=1}^{l} (\mu_i - a_i)^2 eq. 6

T_{h+1} = \arg\max_{T_k} \sum_{i=1}^{l} \left| \left({}^{h}\epsilon(t_i) - {}^{h}\hat{\epsilon}\right) e^{-j 2\pi t_i / T_k} \right| eq. 7

T_{\Sigma}(n) = \sum_{k=1}^{K} \sum_{i=1}^{l} \left| \left({}^{h}\epsilon(t_i) - {}^{h}\hat{\epsilon}\right) e^{-j 2\pi t_i / T_k} \right| eq. 8

Here {}^{h}\hat{\epsilon} is the mean of the error series eq. 7. The paper does not define the index set of K in eq. 8; see Pitfalls.

# Fit the hypertime model  [§3.4] [§3.5] [§3.6] [§3.7]
# Input:  values (l,), locations (l, m), times (l,)
# Output: the last model that improved the error, and its periods

def fit_hypertime(values, locations, times, candidates):
    # Step I: start with no periods; each vector holds (a, x)  [§3.4]
    features = concatenate(values, locations)     # (l, 1 + m)
    periods = []
    best_error = None
    best_model = None
    best_periods = []
    while True:
        # Step II: fit a Gaussian mixture on the current vectors  [§3.5]
        mixture = fit_mixture(features)           # clustering: [§3.8]
        # Step III: scale the model so its mean matches the data  [§3.6]
        scale = scaling_factor(mixture, values, locations, times)
        # Step III: measure the training error of the scaled model  [§3.6]
        error = squared_error(mixture, scale, values, locations, times)
        # Stop when the error does not fall; keep the previous model  [§3.6]
        if best_error is not None and error >= best_error:
            return best_model, best_periods
        best_error = error
        best_model = (mixture, scale)
        best_periods = list(periods)
        # Step IV: find the period that best explains the model error  [§3.7]
        predicted = mean_prediction(mixture, scale, locations, times)
        errors = predicted - values
        period = most_prominent_period(errors, times, candidates)
        periods.append(period)
        # Step V: add cos and sin of time for that period  [§3.4] [eq. 1]
        features = extend_with_time(features, times, period)

# Most prominent period of the error series  [§3.7] [eq. 7]
# Input:  errors (l,), times (l,)
# Output: one period T; the candidate set is not stated

def most_prominent_period(errors, times, candidates):
    # Remove the mean error before the spectral scan  [§3.7]
    centred = errors - mean(errors)
    # Score each candidate period by the spectral magnitude  [§3.7] [eq. 7]
    scores = [spectral_score(centred, times, T) for T in candidates]
    return candidates[argmax(scores)]


def spectral_score(centred, times, period):
    # Magnitude of the sum of complex terms (intended reading, see Pitfalls)
    # [§3.7] [code: frenap/src/CFrelement.cpp#L119-L129]
    terms = centred * exp(-2j * pi * times / period)
    return abs(sum(terms))

# Hypertime extension for one period  [§3.4] [eq. 1]
# Input:  features (l, d), times (l,), period T
# Output: features (l, d + 2)

def extend_with_time(features, times, period):
    # Map time onto a unit circle for this period  [§3.4]
    angle = 2 * pi * times / period
    return concatenate(features, cos(angle), sin(angle))

# Predict p(a | x, t) for one place and time  [§3.6] [eq. 2]
# Input:  model, location x, time t, grid of candidate values a_grid
# Output: probabilities over a_grid that sum to one

def predict_distribution(model, location, time, a_grid):
    # Evaluate the density at each candidate value; the model projects time
    # onto the stored periods internally  [§3.5] [eq. 2]
    densities = [model.density(a, location, time) for a in a_grid]
    # Normalise over the grid so the values sum to one  [§3.6]
    total = sum(densities)
    return [d / total for d in densities]

Hyperparameters

Values not stated in the text are marked "not stated". Experiment sample counts are given per dataset.

Results

Author-reported. The text gives no numeric results; every quantitative result is in a figure. Each row lists the setup, the baselines, and what the text says. Baselines are Mean, Hist, FreMEn and the hypertime variants.

The conclusion states "significantly better performance than the previous state of the art" §5. The text does not name the state of the art in that sentence, and the statistical tests are in the figures.

Paper vs code

No official code.

What was searched:

1. Links in the paper. The conclusion names two project sites: fremen.uk (the DNS lookup failed in our fetch) and chronorobotics.tk, which redirects to chronorobotics.fel.cvut.cz. That site has a FreMEn software card that links only to an internal page, with no repository for hypertime §5.
2. GitHub. A repository search for "hypertime fremen" returned zero results. The GitHub account gestom holds a fremen repository, a fork of strands-project/fremen, licensed MIT with the copyright line "Tomas Krajnik, 2014". We cloned it at commit 1ebf84e7d0ecb9626bda5e46f1e510c3474b8170. It contains FreMEn only. Searches for hypertime, HyT, and k-means or EM code found nothing.

So the hypertime method, HyT-EM and HyT-KM have no released code in what we could reach. The FreMEn baseline code is the nearest thing. The periodicity scan in its spectral step CFrelement.cpp adds the cosine and sine terms of each sample over the frequency list, with the signal's mean removed. The amplitude is the squared magnitude of those sums CFrelement.cpp, and it is normalised by the signal length CFrelement.cpp. This is FreMEn, not the hypertime method, so do not treat it as a reference for eq. 7 or eq. 8.

Pitfalls

• Eq. 7 as printed does not depend on the candidate period. The absolute value sits inside the sum, so each term has the magnitude of the error sample alone, whatever the candidate period. Every candidate then scores the same, and the argmax is decided only by ties. The FreMEn code computes the magnitude of the summed terms CFrelement.cpp, which is the reading used in the pseudocode above. This is an inference, not something the paper states.
• Eq. 3 is not the same as the rule in the text. The text asks that the model's average value over the training samples equal the measured average. The printed formula weights the denominator by a_i. A reading with the sum of the mixture values in the denominator would match the text, but the paper does not say which was used.
• The error is called a mean squared error but is a sum §3.6 eq. 6. The ordering of models is unchanged, because the sample count is fixed, but any absolute error values reported would differ by a factor of l.
• The stopping rule uses training error. Each added periodicity can only make the in-sample fit look better, so E_h will often fall. The paper uses no held-out split for this choice. Models with extra periods may overfit.
• The first comparison has nothing to compare against. The text does not say what happens after the h = 0 model, beyond comparing E_h with E_(h−1) §3.4 §3.6.
• Undefined sets. The candidate periods for eq. 7 are not given. In eq. 8 the sum over k is not defined, so it is unclear whether it uses the same candidate set §3.8.
• The clustering rule in HyT-KM is hard to read. The text accepts n+1 clusters when the spectral sum for n is larger than for n+1 §3.8 eq. 8. It does not say why a larger sum should be preferred, and the direction looks unexpected. Implement it as written and test it.
• Mixed metrics inside EM. HyT-KM uses cosine distance for the time dimensions §3.8, but a Gaussian mixture needs a density. How the cosine distance enters the EM update is not stated. HyT-EM uses the OpenCV EM implementation, so its details come from that library §3.8.
• Numerical instability is the paper's main issue. The text reports that many algorithms became unstable as periodicities were added §3.8 §5. The restart rule for HyT-EM is not given in enough detail to reproduce.
• Units of time are not stated. The text does not say what time origin or unit is used. A period has to be in the same units as t §3.4 eq. 1.
• Prediction needs a grid over a. The grid range and resolution are not given §3.6.
• Scales of the dimensions. The Euclidean and cosine dimensions are mixed in one model. The text does not say whether the values a, x and the periodic coordinates are normalised §3.8.
• Naming. The experiment section calls the cosine-distance variant HyT-KN in one place, while the rest of the paper uses HyT-KM §4 intro §3.8.
• Velocity is a bounded value. The FreMEn baseline for velocity is applied to values in [0, 1] §4.3. The paper does not say whether the hypertime model was bounded in the same way.
• Sampling bias. The authors state that the learned distribution depends on where and when the robot takes measurements §5. Predictions reflect the robot's sampling as well as the environment.
• Equation numbers in this card were counted from the LaTeX source, in order of appearance. Check them against the compiled PDF before citing one outside this wiki.
• Authors. The arXiv metadata lists six authors. The LaTeX source lists eight, adding Oscar Martinez Mozos and George Broughton. The author list in the attribution follows the source.

Lineage

• Builds on: FreMEn, Krajnik et al. (the paper's reference [fremen]). FreMEn finds periodicities in the frequency domain and models one binary state at a time §2 §3.7. The arXiv record for FreMEn is not in this wiki yet.
• Compared against: Mean, Hist_n (histogram per time of day), FreMEn_m, and the hypertime variants HyT-EM_k and HyT-KM §4 intro.
• Related: spatio-temporal occupancy models with Gaussian mixtures §2 (Kucner et al., cited in the paper; not in this wiki).
• Superseded by: not known from content already in this wiki.