Multi-Scale Activity Estimation with Spatial Abstractions

07/11/2017
Publication GSI2017
OAI : oai:www.see.asso.fr:17410:22432
contenu protégé  Document accessible sous conditions - vous devez vous connecter ou vous enregistrer pour accéder à ou acquérir ce document.
- Accès libre pour les ayants-droit
 

Résumé

Estimation and forecasting of dynamic state are fundamental to the design of autonomous systems such as intelligent robots. State-ofthe art algorithms, such as the particle lter, face computational limitations when needing to maintain beliefs over a hypothesis space that is made large by the dynamic nature of the environment. We propose an algorithm that utilises a hierarchy of such lters, exploiting a ltration arising from the geometry of the underlying hypothesis space. In addition to computational savings, such a method can accommodate the availability of evidence at varying degrees of coarseness.We show, using synthetic trajectory datasets, that our method achieves a better normalised error in prediction and better time to convergence to a true class when compared against baselines that do not similarly exploit geometric structure.

Multi-Scale Activity Estimation with Spatial Abstractions

Collection

application/pdf Multi-Scale Activity Estimation with Spatial Abstractions Majd Hawasly, Florian T. Pokorny, Subramanian Ramamoorthy
Détails de l'article
contenu protégé  Document accessible sous conditions - vous devez vous connecter ou vous enregistrer pour accéder à ou acquérir ce document.
- Accès libre pour les ayants-droit

Estimation and forecasting of dynamic state are fundamental to the design of autonomous systems such as intelligent robots. State-ofthe art algorithms, such as the particle lter, face computational limitations when needing to maintain beliefs over a hypothesis space that is made large by the dynamic nature of the environment. We propose an algorithm that utilises a hierarchy of such lters, exploiting a ltration arising from the geometry of the underlying hypothesis space. In addition to computational savings, such a method can accommodate the availability of evidence at varying degrees of coarseness.We show, using synthetic trajectory datasets, that our method achieves a better normalised error in prediction and better time to convergence to a true class when compared against baselines that do not similarly exploit geometric structure.
Multi-Scale Activity Estimation with Spatial Abstractions

Métriques

0
0
3 Mo
 application/pdf
bitcache://08346381d51a21a4fe12710777c4ec119aab3d07

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors Platine

alanturinginstitutelogo.png
logothales.jpg

Sponsors Bronze

logo_enac-bleuok.jpg
imag150x185_couleur_rvb.jpg

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors

smai.png
gdrmia_logo.png
gdr_geosto_logo.png
gdr-isis.png
logo-minesparistech.jpg
logo_x.jpeg
springer-logo.png
logo-psl.png

Organisateurs

logo_see.gif
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/17410/22432</identifier><creators><creator><creatorName>Majd Hawasly</creatorName></creator><creator><creatorName>Florian T. Pokorny</creatorName></creator><creator><creatorName>Subramanian Ramamoorthy</creatorName></creator></creators><titles>
            <title>Multi-Scale Activity Estimation with Spatial Abstractions</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2018</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 3 Mar 2018</date>
	    <date dateType="Updated">Sat 3 Mar 2018</date>
            <date dateType="Submitted">Tue 13 Nov 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">08346381d51a21a4fe12710777c4ec119aab3d07</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>37106</version>
        <descriptions>
            <description descriptionType="Abstract">Estimation and forecasting of dynamic state are fundamental to the design of autonomous systems such as intelligent robots. State-ofthe art algorithms, such as the particle lter, face computational limitations when needing to maintain beliefs over a hypothesis space that is made large by the dynamic nature of the environment. We propose an algorithm that utilises a hierarchy of such lters, exploiting a ltration arising from the geometry of the underlying hypothesis space. In addition to computational savings, such a method can accommodate the availability of evidence at varying degrees of coarseness.We show, using synthetic trajectory datasets, that our method achieves a better normalised error in prediction and better time to convergence to a true class when compared against baselines that do not similarly exploit geometric structure.
</description>
        </descriptions>
    </resource>
.

Multi-Scale Activity Estimation with Spatial Abstractions Majd Hawasly1? , Florian T. Pokorny2 , and Subramanian Ramamoorthy3 1 FiveAI Inc., Edinburgh, United Kingdom m.hawasly@five.ai 2 KTH Royal Institute of Technology, Stockholm, Sweden 3 School of Informatics, The University of Edinburgh, Edinburgh, United Kingdom Abstract. Estimation and forecasting of dynamic state are fundamental to the design of autonomous systems such as intelligent robots. State-of- the-art algorithms, such as the particle filter, face computational limita- tions when needing to maintain beliefs over a hypothesis space that is made large by the dynamic nature of the environment. We propose an algorithm that utilises a hierarchy of such filters, exploiting a filtration arising from the geometry of the underlying hypothesis space. In addition to computational savings, such a method can accommodate the availabil- ity of evidence at varying degrees of coarseness. We show, using synthetic trajectory datasets, that our method achieves a better normalised error in prediction and better time to convergence to a true class when com- pared against baselines that do not similarly exploit geometric structure. 1 Introduction Autonomous agents acting in dynamic environments need the capacity to make predictions about the environment within which they are acting, so as to take actions that are suited to the present world state. Traditionally, tools for state estimation are geared to the case wherein uncertainty arises from noise in the dynamics or sensorimotor processes. For example, the particle filter is a state estimation method utilising a nonparametric representation of beliefs over the state space, used extensively in robotics. However, in problems involving spatial activity, e.g., robot navigation, the underlying dynamics are best described in a hierarchical fashion, as movement is not just determined by local physical laws and noise characteristics, but also by longer-term goals and preferences. This has a few implications for predictive models: we require techniques that 1) accept evidence at varying scales - from very precise position measurements to coarser forms of knowledge, e.g. human feedback, and 2) make predictions at multiple scales to support decision making. These form the primary focus of this paper. Early models of large-scale spatial navigation [5] considered ways in which multiple representations, ranging from coarse and intuitive topological notions of connectivity between landmarks to a more detailed metrical and control level de- scription of action selection, could be brought together in a coherent framework ? At the time of this study, the first author was with The University of Edinburgh. and implemented on robots. Other recent methods, e.g. [1, 3], propose ways in which control vector fields could be abstracted so as to support reasoning about larger-scale tasks. While these works provide useful inspiration, the hierarchy in these methods is often statically defined by the designer, while in many appli- cations it is of interest to learn it directly from data, e.g. to enable continual adaptation over time. Also, these approaches are often silent on how best to integrate tightly with Bayesian belief estimates, such as within a particle filter. There is indeed prior work on the notion of hierarchy in state estimation with particle filters. For instance, Verma et al. [11] define a variable resolution particle filter for operation in large state spaces, where chosen states are aggregated to reduce the complexity of the filter. Brandao et al. [2] devise a subspace hierar- chical particle filter wherein state estimation can be run in parallel with factored parallel computation. Other ways to factoring computation exist, e.g. [6, 10], and a hierarchy of feature encodings can be used [13]. However, to the best of our knowledge, no prior method allows tracking a process on multiple scales at once and accepts evidence with variable resolutions. In this paper, we learn a spatial hierarchy directly from input trajectories, using which we devise a novel construction of a bank of particle filters - one at each scale in a geometric filtration - which maintain consistent beliefs over the trajectories as a whole and, through that, over the state space. We present an agglomerative clustering scheme [7] using the Fréchet distance between trajec- tories [4] to compute a tree-structured representation of trajectory classes that correspond to incrementally-coarser partitions of the underlying space. This is inspired by persistent homology on trajectories [8, 9] whose output is also such a hierarchical representation. We then define a linear dynamics model at each of the levels of the hierarchy based on the subset of trajectories they represent, and show how that can be used with a stream of observations to provide updates to the probability that the system is following the dynamics associated with each of the abstracted trajectory classes. This construction of the filter allows us to fluently incorporate readings of varying resolution if they were accompanied by an indication of the coarseness with which the observation is to be interpreted. We show that our proposed method performs better than baselines both in terms of normalised error in prediction with respect to the ground truth, and in terms of the time taken for the belief to converge to the true trajectory of a class (where convergence is defined with respect to the resolution of the prediction being considered). We perform experiments with synthetic datasets which brings out the qualitative behaviour of the procedure in a visually intuitive manner. 2 Multiscale Hierarchy of Particle Filters The Multiscale Hierarchy of Particle Filters (MHPF) is a bank of consistent particle filters defined over abstractions of the state space induced by example trajectories. The lowest level of this hierarchy consists of the complete set of trajectories with cardinality equal to the size of the trajectory dataset, while each other abstract level has coarser descriptions of the trajectory shape defined by equivalence class of similar trajectories for increasing thresholds. With a particle filter defined at each level, this inclusion property of the representation allows evidence at various degrees of coarseness to be incorporated into the full bank of filters while maintaining consistency across all levels, see Fig. 2. Construction To create a filtration of spatial abstractions from trajectories we consider agglomerative hierarchical clustering [12] by means of a trajectory distance measure. In this paper, we use the discrete Fréchet distance [4]: for two discretised d-dimensional trajectories τ1 : [0, m] → Rd and τ2 : [0, n] → Rd , the distance δF (τ1, τ2) = infα,β maxj≤m+n δE(τ1(α(j)), τ2(β(j))), where α and β are discrete, monotonic re-parametrisations α : [1 : m + n] → [0 : m], β : [1 : m + n] → [0 : n] which align the trajectories to each other point-wise, and δE(., .) is Euclidean distance. Thus, δF corresponds to the maximal point- wise distance between optimal reparameterisations of τ1 and τ2, which can be computed efficiently using dynamic programming in O(mn) time [4]. Let D be the distance matrix of the input trajectories, Di,j = Dj,i = δF (τi, τj). A single-linkage hierarchical agglomerative clustering of D results in a tree T of trajectory clusters in which the leaves are the single trajectories, while every other tree layer is created when the pair with the smallest distance from the previous layer combine together (Fig. 2). If τi and τj are such a pair, we call the new cluster τij a parent to its constituents and write τij = ρ(τi) = ρ(τj). Let the birth index b be that minimum distance that indexes the creation of a layer (e.g., bij = Di,j for τij), and the death index d be the distance at which a cluster is subsumed to its parent (e.g., di