Towards lifelong navigation and mapping in an office environment

This paper addresses the challenge of developing robots that map and navigate autonomously in real world, dynamic environments throughout the robot’s entire lifetime – the problem of lifelong navigation. Static mapping algorithms can produce highly accurate maps, but have found few applications in real environments that are in constant flux. Environments change in many ways: both rapidly and gradually, transiently and permanently, geometrically and in appearance. This paper demonstrates a biologically inspired navigation algorithm, RatSLAM, that uses principles found in rodent neural circuits. The algorithm is demonstrated in an office delivery challenge where the robot was required to perform mock deliveries to goal locations in two different buildings. The robot successfully completed 1177 out of 1178 navigation trials over 37 hours of around the clock operation spread over 11 days.

Autonomous aerial navigation and tracking of marine animals

In this paper, we describe the development of an independent and on-board visual servoing system which allows a computationally impoverished aerial vehicle to autonomously identify and track a moving surface target. Our image segmentation and target identification algorithms were developed with the specific task of monitoring whales at sea but could be adapted for other targets. Observing whales is important for many marine biology tasks and is currently performed manually from the shore or from boats. We also present hardware experiments which demonstrate the capabilities of our algorithms for object identification and tracking that enable a flying vehicle to track a moving target.

Graph rigidity for near-coplanar structure from motion

Recent algorithms for monocular motion capture (MoCap) estimate weak-perspective camera matrices between images using a small subset of approximately-rigid points on the human body (i.e. the torso and hip). A problem with this approach, however, is that these points are often close to coplanar, causing canonical linear factorisation algorithms for rigid structure from motion (SFM) to become extremely sensitive to noise. In this paper, we propose an alternative solution to weak-perspective SFM based on a convex relaxation of graph rigidity. We demonstrate the success of our algorithm on both synthetic and real world data, allowing for much improved solutions to marker less MoCap problems on human bodies. Finally, we propose an approach to solve the two-fold ambiguity over bone direction using a k-nearest neighbour kernel density estimator.

Using incomplete online metric maps for topological exploration with the Gap Navigation Tree

This paper presents a general, global approach to the problem of robot exploration, utilizing a topological data structure to guide an underlying Simultaneous Localization and Mapping (SLAM) process. A Gap Navigation Tree (GNT) is used to motivate global target selection and occluded regions of the environment (called “gaps”) are tracked probabilistically. The process of map construction and the motion of the vehicle alters both the shape and location of these regions. The use of online mapping is shown to reduce the difficulties in implementing the GNT.

A two week persistent navigation and mapping experiment using RatSLAM : insights and current developments

One of the major challenges in achieving long term robot autonomy is the need for a SLAM algorithm that can perform SLAM over the operational lifetime of the robot, preferably without human intervention or supervision. In this paper we present insights gained from a two week long persistent SLAM experiment, in which a Pioneer robot performed mock deliveries in a busy office environment. We used the biologically inspired visual SLAM system, RatSLAM, combined with a hybrid control architecture that selected between exploring the environment, performing deliveries, and recharging. The robot performed more than a thousand successful deliveries with only one failure (from which it recovered), travelled more than 40 km over 37 hours of active operation, and recharged autonomously 23 times. We discuss several issues arising from the success (and limitations) of this experiment and two subsequent avenues of work.

Modeling perceived collision risk in port water navigation

An increase in the likelihood of navigational collisions in port waters has put focus on the collision avoidance process in port traffic safety. The most widely used on-board collision avoidance system is the automatic radar plotting aid which is a passive warning system that triggers an alert based on the pilot’s pre-defined indicators of distance and time proximities at the closest point of approaches in encounters with nearby vessels. To better help pilot in decision making in close quarter situations, collision risk should be considered as a continuous monotonic function of the proximities and risk perception should be considered probabilistically. This paper derives an ordered probit regression model to study perceived collision risks. To illustrate the procedure, the risks perceived by Singapore port pilots were obtained to calibrate the regression model. The results demonstrate that a framework based on the probabilistic risk assessment model can be used to give a better understanding of collision risk and to define a more appropriate level of evasive actions.

Statistical analysis of conflict involvements in port water navigation

With increasing rate of shipping traffic, the risk of collisions in busy and congested port waters is likely to rise. However, due to low collision frequencies in port waters, it is difficult to analyze such risk in a sound statistical manner. A convenient approach of investigating navigational collision risk is the application of the traffic conflict techniques, which have potential to overcome the difficulty of obtaining statistical soundness. This study aims at examining port water conflicts in order to understand the characteristics of collision risk with regard to vessels involved, conflict locations, traffic and kinematic conditions. A hierarchical binomial logit model, which considers the potential correlations between observation-units, i.e., vessels, involved in the same conflicts, is employed to evaluate the association of explanatory variables with conflict severity levels. Results show higher likelihood of serious conflicts for vessels of small gross tonnage or small overall length. The probability of serious conflict also increases at locations where vessels have more varied headings, such as traffic intersections and anchorages; becoming more critical at night time. Findings from this research should assist both navigators operating in port waters as well as port authorities overseeing navigational management.

Modeling collision avoidance decisions in navigation

Due to grave potential human, environmental and economical consequences of collisions at sea, collision avoidance has become an important safety concern in navigation. To reduce the risk of collisions at sea, appropriate collision avoidance actions need to be taken in accordance with the regulations, i.e., International Regulations for Preventing Collisions at Sea. However, the regulations only provide qualitative rules and guidelines, and therefore it requires navigators to decide on collision avoidance actions quantitatively by using their judgments which often leads to making errors in navigation. To better help navigators in collision avoidance, this paper develops a comprehensive collision avoidance decision making model for providing whether a collision avoidance action is required, when to take action and what action to be taken. The model is developed based on three types of collision avoidance actions, such as course change only, speed change only, and a combination of both. The model has potential to reduce the chance of making human error in navigation by assisting navigators in decision making on collision avoidance actions.

SeqSLAM : visual route-based navigation for sunny summer days and stormy winter nights

Learning and then recognizing a route, whether travelled during the day or at night, in clear or inclement weather, and in summer or winter is a challenging task for state of the art algorithms in computer vision and robotics. In this paper, we present a new approach to visual navigation under changing conditions dubbed SeqSLAM. Instead of calculating the single location most likely given a current image, our approach calculates the best candidate matching location within every local navigation sequence. Localization is then achieved by recognizing coherent sequences of these “local best matches”. This approach removes the need for global matching performance by the vision front-end - instead it must only pick the best match within any short sequence of images. The approach is applicable over environment changes that render traditional feature-based techniques ineffective. Using two car-mounted camera datasets we demonstrate the effectiveness of the algorithm and compare it to one of the most successful feature-based SLAM algorithms, FAB-MAP. The perceptual change in the datasets is extreme; repeated traverses through environments during the day and then in the middle of the night, at times separated by months or years and in opposite seasons, and in clear weather and extremely heavy rain. While the feature-based method fails, the sequence-based algorithm is able to match trajectory segments at 100% precision with recall rates of up to 60%.

Fast tessellated solid navigation in GEANT4

Navigation through tessellated solids in GEANT4 can degrade computational performance, especially if the tessellated solid is large and is comprised of many facets. Redefining a tessellated solid as a mesh of tetrahedra is common in other computational techniques such as finite element analysis as computations need only consider local tetrahedrons rather than the tessellated solid as a whole. Here within we describe a technique that allows for automatic tetrahedral meshing of tessellated solids in GEANT4 and the subsequent loading of these meshes as assembly volumes; loading nested tessellated solids and tetrahedral meshes is also examined. As the technique makes the geometry suitable for automatic optimisation using smartvoxels, navigation through a simple tessellated volume has been found to be more than two orders of magnitude faster than that through the equivalent tessellated solid. Speed increases of more than two orders of magnitude were also observed for a more complex tessellated solid with voids and concavities. The technique was benchmarked for geometry load time, simulation run time and memory usage. Source code enabling the described functionality in GEANT4 has been made freely available on the Internet.

Graph-based concept weighting for medical information retrieval

This paper presents a graph-based method to weight medical concepts in documents for the purposes of information retrieval. Medical concepts are extracted from free-text documents using a state-of-the-art technique that maps n-grams to concepts from the SNOMED CT medical ontology. In our graph-based concept representation, concepts are vertices in a graph built from a document, edges represent associations between concepts. This representation naturally captures dependencies between concepts, an important requirement for interpreting medical text, and a feature lacking in bag-of-words representations. We apply existing graph-based term weighting methods to weight medical concepts. Using concepts rather than terms addresses vocabulary mismatch as well as encapsulates terms belonging to a single medical entity into a single concept. In addition, we further extend previous graph-based approaches by injecting domain knowledge that estimates the importance of a concept within the global medical domain. Retrieval experiments on the TREC Medical Records collection show our method outperforms both term and concept baselines. More generally, this work provides a means of integrating background knowledge contained in medical ontologies into data-driven information retrieval approaches.

Expander graph based key distribution mechanisms in wireless sensor networks

Secure communications between large number of sensor nodes that are randomly scattered over a hostile territory, necessitate efficient key distribution schemes. However, due to limited resources at sensor nodes such schemes cannot be based on post deployment computations. Instead, pairwise (symmetric) keys are required to be pre-distributed by assigning a list of keys, (a.k.a. key-chain), to each sensor node. If a pair of nodes does not have a common key after deployment then they must find a key-path with secured links. The objective is to minimize the keychain size while (i) maximizing pairwise key sharing probability and resilience, and (ii) minimizing average key-path length. This paper presents a deterministic key distribution scheme based on Expander Graphs. It shows how to map the parameters (e.g., degree, expansion, and diameter) of a Ramanujan Expander Graph to the desired properties of a key distribution scheme for a physical network topology.

Analyzing the effectiveness of graph metrics for anomaly detection in online social networks

Online social networks can be modelled as graphs; in this paper, we analyze the use of graph metrics for identifying users with anomalous relationships to other users. A framework is proposed for analyzing the effectiveness of various graph theoretic properties such as the number of neighbouring nodes and edges, betweenness centrality, and community cohesiveness in detecting anomalous users. Experimental results on real-world data collected from online social networks show that the majority of users typically have friends who are friends themselves, whereas anomalous users’ graphs typically do not follow this common rule. Empirical analysis also shows that the relationship between average betweenness centrality and edges identifies anomalies more accurately than other approaches.

Data requirements and graph data structures for a multi-modal, multi-objective trip planner

Traffic congestion has a significant impact on the economy and environment. Encouraging the use of multimodal transport (public transport, bicycle, park’n’ride, etc.) has been identified by traffic operators as a good strategy to tackle congestion issues and its detrimental environmental impacts. A multi-modal and multi-objective trip planner provides users with various multi-modal options optimised on objectives that they prefer (cheapest, fastest, safest, etc) and has a potential to reduce congestion on both a temporal and spatial scale. The computation of multi-modal and multi-objective trips is a complicated mathematical problem, as it must integrate and utilize a diverse range of large data sets, including both road network information and public transport schedules, as well as optimising for a number of competing objectives, where fully optimising for one objective, such as travel time, can adversely affect other objectives, such as cost. The relationship between these objectives can also be quite subjective, as their priorities will vary from user to user. This paper will first outline the various data requirements and formats that are needed for the multi-modal multi-objective trip planner to operate, including static information about the physical infrastructure within Brisbane as well as real-time and historical data to predict traffic flow on the road network and the status of public transport. It will then present information on the graph data structures representing the road and public transport networks within Brisbane that are used in the trip planner to calculate optimal routes. This will allow for an investigation into the various shortest path algorithms that have been researched over the last few decades, and provide a foundation for the construction of the Multi-modal Multi-objective Trip Planner by the development of innovative new algorithms that can operate the large diverse data sets and competing objectives.

One-stop government portals : transformation or navigation?

E-government is seen as a promising approach for governments to improve their service towards citizens and become more cost-efficient in service delivery. This is often combined with one-stop government, which is a citizen-oriented approach stressing integrated provision of services from multiple departments via a single access point, the one-stop government portal. While the portal concept is gaining prominence in practice, there is little know about its status in academic literature. This hinders academics in building an accumulated body of knowledge around the concept and makes it hard for practitioners to access relevant academic insights on the topic. The objective of this study is to identify and understand the key themes of the one-stop government portal concept in academic, e-government research. A holistic analysis is provided by addressing different viewpoints: social-political, legal, organizational, user, security, service, data & information, and technical. As overall finding we conclude that there are two different approaches: a more pragmatic approach focuses on quick wins in particular related to usability and navigation and a more ambitious, transformational approach having far reaching social-political, legal, organizational implications.