Publications

A Machine Learning Approach to Meter Placement for Power Quality Estimation in Smart Grid

(2015)

Authors: Sardar Ali, Kui Wu, Kyle Weston, Dimitri Marinakis
Abstract: Due to the high measuring cost, the monitoring of power quality is non-trivial. This paper is aimed at reducing the cost of power quality monitoring in power network. Using a real-world power quality dataset, the paper adopts a learnfrom-data approach to obtain a device latent feature model, which captures the device behavior as a power quality transition function. With the latent feature model, the power network could be modeled, in analogy, as a data-driven network, which presents the opportunity to use the well-investigated network monitoring and data estimation algorithms to solve the network quality monitoring problem in power grid. Based on this network model, algorithms are proposed to intelligently place measurement devices on suitable power links to reduce the uncertainty of power quality estimation on unmonitored power links. The meter placement algorithms use entropy-based measurements and Bayesian network models to identify the most suitable power links for power quality meter placement. Evaluation results on various simulated networks including IEEE distribution test feeder system show that the meter placement solution is efficient, and has the potential to significantly reduce the uncertainty of power quality values on unmonitored power links.

Co-Location Electrical Architecture

(2014)

Authors: Martin A. Hancock, Matthew Stanlake, Peter Cowan, Gorp John C. Van, David KIDD, Hugh Lindsay, John TOFFLER, Catherine GAMROTH, Kui WU, Dimitri Marinakis
Abstract: A system and method for managing an electrical distribution system in a facility is disclosed. In one aspect, the method may include receiving at a computer system from a monitoring system data related to actual energy use of components of the electrical distribution system, receiving at the computer system a request for a modification to the electrical distribution system, using the computer system, providing a revised electrical distribution system design based on the request and the data related to actual energy use using a system optimization function for the electrical distribution system, modifying the electrical distribution system in accordance with the revised electrical distribution system design to provide a modified electrical distribution system in the facility, and receiving at the computer system from the monitoring system data related to actual energy use of components of the modified electrical distribution system.

The Range Beacon Placement Problem for Robot Navigation

(2014)

Authors: River Allen, Neil MacMillan, Dimitri Marinakis, Rahnuma Islam Nishat, Rayhan Rahman, Sue Whitesides
Abstract: Instrumentation of an environment with sensors can provide an effective and scalable localization solution for robots. Where GPS is not available, beacons that provide position estimates to a robot must be placed effectively in order to maximize a robots navigation accuracy and robustness. Sonar range-based beacons are reasonable candidates for low cost position estimate sensors. In this paper we explore heuristics derived from computational geometry to estimate the effectiveness of sonar beacon deployments given a predefined mobile robot path. Results from numerical simulations and experimentation demonstrate the effectiveness and scalability of our approach.

Trajectory Inference Using a Motion Sensing Network

(2014)

Authors: Doug Cox, Darren Fairall, Neil MacMillan, Dimitri Marinakis, David Meger, Saamaan Pourtavakoli, Kyle Weston
Abstract: This paper addresses the problem of inferring human trajectories through an environment using low frequency, low fidelity data from a sensor network. We present a novel “recombine” proposal for Markov Chain construction and use the new proposal to devise a probabilistic trajectory inference algorithm that generates likely trajectories given raw sensor data. We also propose a novel, low-power, long range, 900 MHz IEEE 802.15.4 compliant sensor network that makes outdoors deployment viable. Finally, we present experimental results from our deployment at a retail environment.

Systems and Methods for Meter Placement in Power Grid Networks

(2014)

Authors: Dimitri Marinakis, Kui WU, Sardar ALI, Kyle Weston
Abstract: Systems and methods for placement of power meters in a power distribution network are disclosed. In one example, the method comprises modeling the power distribution network as a data-driven network comprising a plurality of nodes and a plurality of power links connecting individual nodes of the plurality of nodes, receiving at a computer system data pertaining to network topology and a number of power meters to be placed in the power distribution network, and calculating, by the computer system, placement of at least one power meter within the power distribution system.

Centralized Route Calcultion for a Multi-Hop Street-light Network

(2013)

Authors: Dimitri Marinakis, Marcus Redivo, Zoltan Varga, Jam Hamidi, Simon H. Lightbody
Abstract: A system and various apparatus and methods performed therein configured for calculating routes touching and monitoring and controlling streetlights includes a multiplicity of streetlight controllers and a local coordinator. Each streetlight controller includes a switch operative to control the operation of a load, a sensor operative to monitor the operation of the load, a processor, and a radio transceiver operative to receive control data and transmit data associated with the streetlight controller. The local coordinator includes a coordinator radio transceiver, and a coordinator processor operative to maintain a list of the multiplicity of streetlight controllers and, cooperatively with the coordinator radio transceiver, exchange messages with any of the multiplicity of streetlight controllers.

Network Optimization for Lightweight Stochastic Scheduling in Underwater Sensor Networks

(2012)

Authors: Dimitri Marinakis, Kui Wu, Ning Ye, and Sue Whitesides
Abstract: In this paper, we examine the merit of a simple and lightweight stochastic transmission strategy based on the ALOHA protocol for underwater wireless sensor networks (UWSNs). We use a stochastic scheduling approach in which time is slotted, and each network component transmits according to some probability during each slot. We present objective functions for assigning the transmission probabilities that are aimed at optimizing network performance with respect to the overall network latency and the overall network reliability. We show that there is an easily distributed heuristic policy based on local network density that works well in practice. We also evaluate our approach using numerical simulations. The evaluation results show that even without using explicit control signaling, our lightweight stochastic scheduling method is effective for data transmission in underwater sensor networks.

A Stochastic Calculus for Network Systems with Renewable Energy Sources

(2012)

Authors: Kui Wu, Yuming Jiang, and Dimitri Marinakis
Abstract: We consider the performance modeling and evaluation of network systems powered with renewable energy sources such as solar and wind energy. Such energy sources largely depend on environmental conditions, which are hard to predict accurately. As such, it may only make sense to require the network systems to support a soft quality of service (QoS) guarantee, i.e., to guarantee a service requirement with a certain high probability. In this paper, we build a solid mathematical foundation to help better understand the stochastic energy constraint and the inherent correlation between QoS and the uncertain energy supply. We utilize a calculus approach to model the cumulative amount of charged energy and the cumulative amount of consumed energy. We derive upper and lower bounds on the remaining energy level based on a stochastic energy charging rate and a stochastic energy discharging rate. By building the bridge between energy consumption and task execution (i.e., service), we study the QoS guarantee under the constraint of uncertain energy sources.

Connecting a Set of Circles with Minimum Sum of Radii

(2011)

Authors: Erin Wolf Chambers, Sandor P. Fekete, Hella-Franziska Hoffmann, Dimitri Marinakis, Joseph S.B. Mitchell, Venkatesh Sirinivasan, Ulrike Stege, Sue Whitesides
Abstract: We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.

Stochastic Scheduling for Underwater Sensor Networks

(2011)

Authors: Dimitri Marinakis, Kui Wu, and Sue Whitesides
Abstract: The context of underwater sensor networks (UWSNs) presents special challenges for data transmission. For that context, we examine the merit of using a simple, stochastic transmission strategy based on the ALOHA protocol. The strategy uses a stochastic scheduling approach in which time is slotted, and each network node broadcasts according to some probability during each time slot. We present a closed-form solution to an objective function that guides the assignment of the broadcast probabilities with respect to overall network reliability. We propose an easily distributed heuristic based on local network density and evaluate our approach using numerical simulations. The evaluation results show that even without using explicit control signalling, our simple stochastic scheduling method performs well for data transmission in UWSNs.

Scheduling Recurring Tasks in Energy Harvesting Sensors

(2011)

Authors: David Audet, Leandro Collares De Oliveira, Neil MacMillan, Dimitri Marinakis, Kui Wu
Abstract: We consider the problem of periodic task scheduling in sensor nodes powered with energy harvesters. In particular, we focus on systems with stochastic energy sources such as solar panels, and we present two energy-aware scheduling algorithms that reduce the likelihood of task violations. Our algorithms, called Smooth to Average Method (STAM) and Smooth to Full Utilization (STFU), are static schedulers that do not require prescience of the incoming energy to operate effectively.

Simultaneous Localization and Environmental Mapping with a Sensor Network

(2011)

Authors: Dimitri Marinakis, Neil MacMillan, River Allen, Sue Whitesides
Abstract: In this paper, we present an algorithm for simultaneously refining a probability distribution function (PDF) for the pose of a sensor network (i.e. the locations of the sensors), and inferring the spatial variations of measured environmental parameters. Our approach iteratively refines a network pose PDF by assuming that environmental parameters vary smoothly. Both our physical experiments, which sensed wireless signal strength as the environmental ariable, and our numerical simulations demonstrate that the approach has promise.

Range-Based Navigation System for Mobile Robot

(2011)

Authors: Neil MacMillan, River Allen, Dimitri Marinakis, Sue Whitesides
Abstract: In this paper we present an algorithm for path planning in a fixed range-only beacon field. We define and calculate entropy values for regions of interest and provide a method for finding “safe,” low-entropy paths between regions. We go on to describe a robotic system for performing range-based localization experiments, developed using inexpensive off the-shelf components. Our system uses a commercial robot as a mobile platform and custom acoustic beacons for ranging.

Explicit Occlusion Reasoning for 3D Object Detection

(2011)

Authors: David Meger, Christian Wojek, Bernt Schiele, James J. Little
Abstract: This paper presents a technique to locate objects in 3D that adapts visual appearance models using explicit visibility analysis. We formulate a Bayesian model for 3D object likelihood based on visual appearance, 3D geometry such as that available from RGB-depth sensors, and structure-from-motion. Learned visual appearance templates for portions of an object allow for strong discrimination even under occlusion. We describe an efficient inference procedure based on data-driven sampling with geometric refinement. Our 3D object detection technique is demonstrated on the publicly available robot-collected UBC Visual Robot Survey dataset, as well as with data from the Microsoft Kinect. Results show that our method improves robustness to occlusion when compared to a state-of-the-art visual category detector.

Mobile 3D Object Detection in Clutter

(2011)

Authors: David Meger and James J. Little
Abstract: This paper presents a method for multi-view 3D robotic object recognition targeted for cluttered indoor scenes. We explicitly model occlusions that cause failures in visual detectors by learning a generative appearance-occlusion model from a training set containing annotated 3D objects, images and point clouds. A Bayesian 3D object likelihood incorporates visual information from many views as well as geometric priors for object size and position. An iterative, sampling based inference technique determines object locations based on the model. We also contribute a novel robot-collected data set with images and point clouds from multiple views of 60 scenes, with over 600 manually annotated 3D objects accounting for over ten thousand bounding boxes. This data has been released to the community. Our results show that our system is able to robustly recognize objects in realistic scenes, significantly improving recognition performance in clutter.

Improving Image Classification by Co-training with Multi-modal Features

(2011)

Authors: Kyle Weston
Abstract: We explore the user of co-training to improve the performance of image classification in the setting where multiple classifiers are used and several types of features are available. Features are assigned to classifiers in an optimal manner using hierarchical clustering with a distance metric based on conditional mutual information. The effect of increasing the number of classifiers is then evaluated by co-training using the assigned feature sets. Experimental results indicate that the feature assigned chosen by the clustering approach afford superior co-training performance in comparison to other logical assignment choices. The results also indicate that increasing the number of classifiers beyond two leads to improved performance provided that the classifiers are sufficiently independent, and are reasonably well balance din terms of labelling ability. Additionally, we explore the effect that the initial training set selection has on co-training performance. We find that the quality of training images has a profound effect on performance and provide recommendations for how best to select these images.

Risk Averse Motion Planning for a Mobile Robot

Authors: Neil MacMillan, River Allen, Dimitri Marinakis, Sue Whitesides
Abstract: Here we consider a pragmatic sample-based motion planning approach for a robot operating in a fixed, rangeonly beacon field. We define and calculate entropy values for regions of interest and provide a method for finding “safe,” risk averse, low-entropy paths between these regions. We include an experimental, real-world assessment of the approach.

Multiple Viewpoint Recognition and Localization

(2010)

Authors: Scott Helmer, David Meger, Marius Muja, James J. Little, David G. Lowe
Abstract: This paper presents a novel approach for labeling objects based on multiple spatially-registered images of a scene. We argue that such a multi-view labeling approach is a better fit for applications such as robotics and surveillance than traditional object recognition where only a single image of each scene is available. To encourage further study in the area, we have collected a data set of well-registered imagery for many indoor scenes and have made this data publicly available. Our multi-view labeling approach is capable of improving the results of a wide variety of image-based classifiers, and we demonstrate this by producing scene labelings based on the output of both the Deformable Parts Model of [1] as well as a method for recognizing object contours which is similar to chamfer matching. Our experimental results show that labeling objects based on multiple viewpoints leads to a significant improvement in performance when compared with single image labeling.

Viewpoint Detection Models for Sequential Embodied Object Category Recognition

(2010)

Authors: David Meger, Ankur Gupta and James J. Little
Abstract: This paper proposes a method for learning viewpoint detection models for object categories that facilitate sequential object category recognition and viewpoint planning. We have examined such models for several state-of-the-art object detection methods. Our learning procedure has been evaluated using an exhaustive multiview category database recently collected for multiview category recognition research. Our approach has been evaluated on a simulator that is based on real images that have previously been collected. Simulation results verify that our viewpoint planning approach requires fewer viewpoints for confident recognition. Finally, we illustrate the applicability of our method as a component of a completely autonomous visual recognition platform that has previously been demonstrated in an object category recognition competition.

Curious George: An Integrated Visual Search Platform

(2010)

Authors: David Meger, Marius Muja, Scott Helmer, Ankur Gupta, Catherine Gamroth, Tomas Hoffman, Matthew Baumann, Tristram Southey, Pooyan Fazli, Walter Wohlkinger, Pooja Viswanathan, James J. Little and David G. Lowe
Abstract: This paper describes an integrated robot system, known as Curious George, that has demonstrated state-of-the-art capabilities to recognize objects in the real world. We describe the capabilities of this system, including: the ability to access web-based training data automatically and in near real-time; the ability to model the visual appearance and 3D shape of a wide variety of object categories; navigation abilities such as exploration, mapping and path following; the ability to decompose the environment based on 3D structure, allowing for attention to be focused on regions of interest; the ability to capture high-quality images of objects in the environment; and finally, the ability to correctly label those objects with high accuracy. The competence of the combined system has been validated by entry into an international competition where Curious George has been among the top performing systems each year. We discuss the implications of such successful object recognition for society, and provide several avenues for potential improvement.

Pure Topological Mapping in Mobile Robotics

(2010)

Authors: Dimitri Marinakis and Gregory Dudek
Abstract: In this paper we investigate a pure form of the topological mapping problem in mobile robotics. We consider the mapping ability of a robot navigating a graph-like world in which it is able to assign a relative ordering to the edges leaving a vertex with reference to the edge by which it arrived, but is unable to associate a unique label with any vertex or edge. Our work extends and builds upon earlier approaches in this problem domain, which are based on constructing an exploration tree of plausible world-models. The main contributions of the paper are: improved exploration strategies that reduce model ambiguity; a new method of searching through consistent models in the exploration tree that maintains a bounded set of likely hypotheses based on the principle of Occam’s Razor; the incorporation of arbitrary feature vectors into the problem formulation; and an investigation of various aspects of this problem through numerical simulations.

The Sentinel Problem for a Multi-hop Sensor Network

(2010)

Authors: Dimitri Marinakis and Sue Whitesides
Abstract: In the context of a multi-hop sensor network alarm application, we define the Sentinel Problem: How can a network of simple devices with limited communication ability signal the occurrence of an event that is capable of disabling the sensors? We present both deterministic and probabilistic methods for solving this problem, and evaluate the methods based on algorithmic correctness, false positive rates, latency, and implementation potential.

Inferring a Probability Distribution Function for the Pose of a Sensor Network using a Mobile Robot

(2009)

Authors: David Meger, Dimitri Marinakis, Ioannis Rekleitis, and Gregory Dudek
Abstract: In this paper we present an approach for localizing a sensor network augmented with a mobile robot which is capable of providing inter-sensor pose estimates through its odometry measurements. We present a stochastic algorithm that samples efficiently from the probability distribution for the pose of the sensor network by employing Rao-Blackwellization and a proposal scheme which exploits the sequential nature of odometry measurements. Our algorithm automatically tunes itself to the problem instance and includes a principled stopping mechanism based on convergence analysis. We demonstrate the favourable performance of our approach compared to that of established methods via simulations and experiments on hardware.

Self-Calibration of a Vision-Based Sensor Network

(2009)

Authors: Dimitri Marinakis and Gregory Dudek.
Abstract: When a network of vision-based sensors is emplaced in an environment for applications such as surveillance or monitoring the spatial
relationships between the sensing units must be inferred or computed for self-calibration purposes. In this paper we describe a technique to solve one aspect of this self-calibration problem: automatically determining the topology and connectivity information of a network of cameras based on a statistical analysis of observed motion in the environment. While the technique can use labels from reliable cameras systems, the algorithm is powerful enough to function using ambiguous tracking data. The method requires no prior knowledge of the relative locations of the cameras and operates under very weak environmental assumptions. Our approach stochastically samples plausible agent trajectories based on a delay model that allows for transitions to and from sources and sinks in the environment. The technique demonstrates considerable robustness both to sensor error and non-trivial patterns of agent motion. The output of the method is a Markov model describing the behavior of agents in the system and the underlying traffic patterns.The concept is demonstrated with simulation data for systems containing up to ten agents and verified with experiments conducted on a six camera sensor network.

Inferring a Probability Distribution Function for the Pose of a Sensor Network using a Mobile Robot

(2009)

Authors: David Meger, Dimitri Marinakis, Ioannis Rekleitis, and Gregory Dudek
Abstract: In this paper we present an approach for localizing a sensor network augmented with a mobile robot which is capable of providing inter-sensor pose estimates through its odometry measurements. We present a stochastic algorithm that samples efficiently from the PDF for the pose of the sensor network by employing Rao-Blackwellization and a proposal scheme which exploits the sequential nature of odometry measurements. Our algorithm automatically tunes itself to the problem instance and includes a principled stopping mechanism based on convergence analysis. We demonstrate the favourable performance of our approach compared to that of established methods via simulations and experiments on hardware.

Automated Spatial-Semantic Modeling with Applications to Place Labeling and Informed Search

(2009)

Authors: Pooja Viswanathan, David Meger, Tristram Southey, James J. Little, Alan Mackworth
Abstract: This paper presents a spatial-semantic modeling system featuring automated learning of object-place relations from an online annotated database, and the application of these relations to a variety of real-world tasks. The system is able to label novel scenes with place information, as we demonstrate on test scenes drawn from the same source as our training set. We have designed our system for future enhancement of a robot platform that performs state-of-the-art object recognition and creates object maps of realistic environments. In this context, we demonstrate the use of spatial-semantic information to perform clustering and place labeling of object maps obtained from real homes. This place information is fed back into the robot system to inform an object search planner about likely locations of a query object. As a whole, this system represents a new level in spatial reasoning and semantic understanding for a physical platform.

Semantic Robot Vision Challenge: Current State and Future Directions

(2009)

Authors: Scott Helmer, David Meger, Pooja Viswanathan, Sancho McCann, Matthew Dockrey, Pooyan Fazli, Tristram Southey, Marius Muja, Michael Joya, Jim Little, David Lowe
Abstract: The Semantic Robot Vision Competition provided an excellent opportunity for our research lab to integrate our many ideas under one umbrella, inspiring both collaboration and new research. The task, visual search for an unknown object, is relevant to both the vision and robotics communities. Moreover, since the interplay of robotics and vision is sometimes ignored, the competition provides a venue to integrate two communities. In this paper, we outline a number of modifications to the competition to both improve the state-of-the-art and increase participation.

Informed Visual Search: Combining Attention and Object Recognition

(2008)

Authors: Per-Erik Forssen, David Meger, Kevin Lai, Scott Helmer, James J. Little, David G. Lowe
Abstract: This paper studies the sequential object recognition problem faced by a mobile robot searching for specific objects within a cluttered environment. In contrast to current state-of-the-art object recognition solutions which are evaluated on databases of static images, the system described in this paper employs an active strategy based on identifying potential objects using an attention mechanism and planning to obtain images of these objects from numerous viewpoints. We demonstrate the use of a bag-of-features technique for ranking potential objects, and show that this measure outperforms geometric matching for invariance across viewpoints. Our system implements informed visual search by prioritising map locations and re-examining promising locations first. Experimental results demonstrate that our system is a highly competent object recognition system that is capable of locating numerous challenging objects amongst distractors.

Heuristic Search Planning to Reduce Exploration Uncertainty

(2008)

Authors: David Meger, Ioannis Rekleitis, and Gregory Dudek
Abstract: The path followed by a mobile robot while mapping an environment (i.e. an exploration trajectory) plays a large role in determining the efficiency of the mapping process and the accuracy of any resulting metric map of the environment. This paper examines some important aspects of path planning in this context: the trade-offs between the speed of the exploration process versus the accuracy of resulting maps; and alternating between exploration of new territory and planning through known maps. The resulting motion planning strategy and associated heuristic are targeted to a robot building a map of an environment assisted by a Sensor Network composed of uncalibrated monocular cameras. An adaptive heuristic exploration strategy based on A∗ search over a combined distance and uncertainty cost function allows for adaptation to the environment and improvement in mapping accuracy. We assess the technique using an illustrative experiment in a real environment and a set of simulations in a parametric family of idealized environments.

Curious George: An Attentive Semantic Robot

(2008)

Authors: David Meger, Per-Erik Forssen, Kevin Lai, Scott Helmer, Sancho McCann, Tristram Southey, Matthew Baumann, James J. Little a David G. Lowe
Abstract: State-of-the-art methods have recently achieved impressive performance for recognising the objects present in large databases of pre-collected images. There has been much less focus on building embodied systems that recognise objects present in the real world. This paper describes an intelligent system that attempts to perform robust object recognition in a realistic scenario, where a mobile robot moving through an environment must use the images collected from its camera directly to recognise objects. To perform successful recognition in this scenario, we have chosen a combination of techniques including a peripheral-foveal vision system, an attention system combining bottom-up visual saliency with structure from stereo, and a localisation and mapping technique. The result is a highly capable object recognition system that can be easily trained to locate the objects of interest in an environment, and subsequently build a spatial-semantic map of the region. This capability has been demonstrated during the Semantic Robot Vision Challenge, and is further illustrated with a demonstration of semantic mapping. We also empirically verify that the attention system outperforms an undirected approach even with a significantly lower number of foveations.

Occam’s Razor Applied to Network Topology Inference

(2008)

Authors: Dimitri Marinakis and Gregory Dudek
Abstract: We present a method for inferring the topology of a sensor network given non-discriminating observations of activity in the monitored region. This is accomplished based on no prior knowledge of the relative locations of the sensors and weak assumptions regarding environmental conditions. Our approach employs a two-level reasoning system made up of a stochastic Expectation Maximization algorithm and a higher level search strategy employing the principle of Occam’s Razor to look for the simplest solution explaining the data. The result of the algorithm is a Markov model describing the behavior of agents in the system and the underlying traffic patterns. Numerical simulations and experimental assessment conducted on a real sensor network suggest that the technique could have promising real world applications in the area of sensor network self-configuration.

Balancing Compressed Sequences

(2008)

Authors: Saamaan Pourtavakoli
Abstract: The performance of communication and storage systems can be improved if the data being sent or stored has certain patterns and structure. In particular, some benefit if the frequency of the symbols is balanced. This includes magnetic and optical data storage devices, as well as future holographic storage systems. Significant research has been done to develop techniques and algorithms to adapt the data (in a reversible manner) to these systems. The goal has been to restructure the data to improve performance while keeping the complexity as low as possible. In this thesis, we consider balancing binary sequences and present its application in holographic storage systems. An overview is given of different approaches, as well as a survey of previous balancing methods. We show that common compression algorithms can be used for this purpose both alone and combined with other balancing algorithms. Simplified models are analyzed using information theory to determine the extent of the compression in this context. Simulation results using standard data are presented as well as theoretical analysis for the performance of the combination of compression with other balancing algorithms.

Hybrid Inference for Sensor Network Localization using a Mobile Robot

(2007)

Authors: Dimitri Marinakis, David Meger, Ioannis Rekleitis, Gregory Dudek
Abstract: In this paper, we consider a hybrid solution to the sensor network position inference problem, which combines a real-time filtering system with information from a more expensive, global inference procedure to improve accuracy and prevent divergence. Many online solutions for this problem make use of simplifying assumptions, such as Gaussian noise models and linear system behaviour and also adopt a filtering strategy which may not use available information optimally. These assumptions allow near real-time inference, while also limiting accuracy and introducing the potential for ill-conditioning and divergence. We consider augmenting a particular realtime estimation method, the extended Kalman filter (EKF), with a more complex, but more highly accurate, inference technique based on Markov Chain Monte Carlo (MCMC) methodology. Conventional MCMC techniques applied to this problem can entail significant and time consuming computation to achieve convergence. To address this, we propose an intelligent bootstrapping process and the use of parallel, communicative chains of different temperatures, commonly referred to as parallel tempering. The combined approach is shown to provide substantial improvement in a realistic simulated mapping environment and when applied to a complex physical system involving a robotic platform moving in an office environment instrumented with a camera sensor network.

Planning, Localization, and Mapping for a Mobile Robot in a Camera Network

(2007)

Authors: David Paul Meger
Abstract: Networks of cameras such as building security systems can be a source of localization information for a mobile robot assuming a map of camera locations as well as calibration information for each camera is available. This thesis describes an automated system to acquire such information. A fully automated camera calibration system uses fiducial markers and a mobile robot in order to drastically improve easeof-use compared to standard techniques. A 6DOF EKF is used for mapping and is validated experimentally over a 50 m hallway environment. Motion planning strategies are considered both in front of a single camera to maximize calibration accuracy and globally between cameras in order to facilitate accurate measurements. For global motion planning, an adaptive exploration strategy based on heuristic search allows compromise between distance traveled and final map uncertainty which provides the system a level of autonomy which could not be obtained with previous techniques.

Topological Mapping with Weak Sensory Data

(2007)

Authors: Gregory Dudek and Dimitri Marinakis
Abstract: In this paper, we consider the exploration of topological environments by a robot with weak sensory capabilities. We assume only that the robot can recognize when it has reached a vertex, and can assign a cyclic ordering to the edges leaving a vertex with reference to the edge it arrived from. Given this limited sensing capability, and without the use of any markers or additional information, we will show that the construction of a topological map is still feasible. This is accomplished through both the exploration strategy which is designed to reveal model inconsistencies and by a search process that maintains a bounded set of believable world models throughout the exploration process. Plausible models are selected through the use of a ranking heuristic function based on the principle of Occam’s Razor. We conclude with numerical simulations demonstrating the performance of the algorithm.

Learning Network Topology from Simple Sensor Data

(2007)

Authors: Dimitri Marinakis, Philippe Giguere, and Gregory Dudek
Abstract: In this paper, we present an approach for recovering a topological map of the environment using only detection events from a deployed sensor network. Unlike other solutions to this problem, our technique operates on timestamp free observational data; i.e. no timing information is exploited by our algorithm except the ordering. We first give a theoretical analysis of this version of the problem, and then we show that by considering a sliding window over the observations, the problem can be re-formulated as a version of set-covering. We present two heuristics based on this set-covering formulation and evaluate them with numerical simulations. The experiments demonstrate that promising results can be obtained using a greedy algorithm.

Topological Mapping through Distributed, Passive Sensors

(2007)

Authors: Dimitri Marinakis and Gregory Dudek
Abstract: In this paper we address the problem of inferring the topology, or inter-node navigability, of a sensor network given non-discriminating observations of activity in the environment. By exploiting motion present in the environment, our approach is able to recover a probabilistic model of the sensor etwork connectivity graph and the underlying traffic trends. We employ a reasoning system made up of a stochastic Expectation Maximization algorithm and a higher level search strategy employing the principle of Occam’s Razor to look for the simplest solution explaining the data. The technique is assessed through numerical simulations and experiments conducted on a real sensor network.

Simultaneous Planning, Localization, and Mapping in a Camera Sensor Network

(2006)

Authors: Ioannis Rekleitis, David Meger, Gregory Dudek
Abstract: In this paper we examine issues of localization, exploration, and planning in the context of a hybrid robot/camera-network system. We exploit the ubiquity of camera networks to use them as a source of localization data. Since the Cartesian position of the cameras in most networks is not known accurately, we consider the issue of how to localize such cameras. To solve this hybrid localization problem, we divide it into a local problem of camera-parameter estimation combined with a global planning and navigation problem. We solve the local camera-calibration problem by using fiducial markers attached to the robot and by selecting robot trajectories in front of each camera that provide good calibration and field-of-view accuracy. We propagate information among the cameras and the successive positions of the robot using an Extended Kalman filter. Finally, we move the robot between the camera positions to explore the network using heuristic exploration strategies. The paper includes experimental data from an indoor office environment as well as tests on simulated data sets.

Probabilistic Self-Localization for Sensor Networks

(2006)

Authors: Dimitri Marinakis and Gregory Dudek
Abstract: This paper describes a technique for the probabilistic self-localization of a sensor network based on noisy inter-sensor range data. Our method is based on a number of parallel instances of Markov Chain Monte Carlo (MCMC). By combining estimates drawn from these parallel chains, we build up a representation of the underlying probability distribution function (PDF) of the network pose. Our approach includes sensor data incrementally in order to avoid local minima and is shown to produce meaningful results efficiently. We return a distribution over sensor locations rather than a single maximum likelihood estimate. This can then be used for subsequent exploration and validation.

A Practical Algorithm for Network Topology Inference

(2006)

Authors: Dimitri Marinakis and Gregory Dudek
Abstract: When a network of robots or static sensors is emplaced in an environment, the spatial relationships between the sensing units must be inferred or computed for most key applications. In this paper we present a Monte Carlo Expectation Maximization algorithm for recovering the connectivity information (i.e. topological map) of a network using only detection events from deployed sensors. The technique is based on stochastically reconstructing samples of plausible agent trajectories allowing for the possibility of transitions to and from sources and sinks in the environment. We demonstrate robustness to sensor error and non-trivial patterns of agent motion. The result of the algorithm is a probabilistic model of the sensor network connectivity graph and the underlying traffic trends. We conclude with results from numerical simulations and an experiment conducted with a heterogeneous sensor network.

Sensor Network Topology Inference

(2005)

Authors: Dimitri Marinakis and Gregory Dudek
Abstract: We present a method for inferring the topology of a sensor network given non-discriminating observations of activity in the monitored region. This is accomplished based on no prior knowledge of the relative locations of the sensors and weak assumptions regarding environmental conditions. Our approach employs a two-level reasoning system made up of a stochastic Expectation Maximization algorithm and a higher level search strategy employing the principle of Occam’s Razor to look for the simplest solution explaining the data. The result of the algorithm is a Markov model describing the behaviour of agents in the system and the underlying traffic patterns. Numerical simulations and experimental assessment conducted on a real sensor network suggest that the technique could have promising real world applications in the area of sensor network self-configuration.

Topology Inference for a Vision-Based Sensor Network

(2005)

Authors: Dimitri Marinakis and Gregory Dudek
Abstract: In this paper we describe a technique to infer the topology and connectivity information of a network of cameras based on observed motion in the environment. While the technique can use labels from reliable cameras systems, the algorithm is powerful enough to function using ambiguous tracking data. The method requires no prior knowledge of the relative locations of the cameras and operates under very weak environmental assumptions. Our approach stochastically samples plausible agent trajectories based on a delay model that allows for transitions to and from sources and sinks in the environment. The technique demonstrates considerable robustness both to sensor error and non-trivial patterns of agent motion. The output of the method is a Markov model describing the behavior of agents in the system and the underlying traffic patterns. The concept is demonstrated with simulation data and verified with experiments conducted on a six camera sensor network.

Learning Sensor Network Topology through Monte Carlo Expection Maximization

(2005)

Authors: Dimitri Marinakis, Gregory Dudek, and David Fleet
Abstract: We consider the problem of inferring sensor positions and a topological (i.e. qualitative) map of an environment given a set of cameras with non-overlapping fields of view. In this way, without prior knowledge of the environment nor the exact position of sensors within the environment, one can infer the topology of the environment, and common traffic patterns within it. In particular, we consider sensors stationed at the junctions of the hallways of a large building. We infer the sensor connectivity graph and the travel times between sensors (and hence the hallway topology) from the sequence of events caused by unlabeled agents (i.e. people) passing within view of the different sensors. We do this based on a first-order semi-Markov model of the agent’s behavior. The paper describes a problem formulation and proposes a stochastic algorithm for its solution. The result of the algorithm is a probabilistic model of the sensor network connectivity graph and the underlying traffic patterns. We conclude with results from numerical simulations.