Driving on Point Clouds: Motion Planning,Trajectory Optimization,and Terrain Assessment in Generic Nonplanar Environments

We present a practical approach to global motion planning and terrain assessment for ground robots in generic three‐dimensional (3D) environments, including rough outdoor terrain, multilevel facilities, and more complex geometries. Our method computes optimized six‐dimensional trajectories compliant with curvature and continuity constraints directly on unordered point cloud maps, omitting any kind of explicit surface reconstruction, discretization, or topology extraction. We assess terrain geometry and traversability on demand during motion planning, by fitting robot‐sized planar patches to the map and analyzing the local distribution of map points. Our motion planning approach consists of sampling‐based initial trajectory generation, followed by precise local optimization according to a custom cost measure, using a novel, constraint‐aware trajectory optimization paradigm. We embed these methods in a complete autonomous navigation system based on localization and mapping by means of a 3D laser scanner and iterative closest point matching, suitable for both static and dynamic environments. The performance of the planning and terrain assessment algorithms is evaluated in offline experiments using recorded and simulated sensor data. Finally, we present the results of navigation experiments in three different environments—rough outdoor terrain, a two‐level parking garage, and a dynamic environment, demonstrating how the proposed methods enable autonomous navigation in complex 3D terrain.     

Navigation your way: from spontaneous independent exploration to dynamic social journeys

In this article, we describe a novel approach to pedestrian navigation using bearing-based haptic feedback. People are guided in the general direction of their destination via a minimal directional cue, but additional exploration is stimulated by varying feedback based on the potential for taking alternative routes. This extreme navigation method removes the complexities of maps and direction following, concentrating on allowing pedestrians to actively explore their surroundings, rather than offering perfect, but passive, turn-by-turn guidance. We simulate and build two mobile prototypes to examine the possible benefits of this approach, then further extend its impact by considering how social media might be incorporated to provide a real-time, dynamically evolving map of physical locations. The successful use of our mobile prototypes is demonstrated in a realistic field trial, and we discuss the results and interesting participant behaviours that were recorded, validating the predictions from their earlier simulation. We continue by simulating the use of publicly posted status updates and pictures as a proxy for location mapping, showing how these methods can produce comparable navigation results to real-world field trials, highlighting their potential as tools for real-world social journeys.     

The effect of different types of navigation assistance on indoor scene memorability

With the rapid growing of wearable computing devices, indoor navigation guidance will become popular in the near future like the GPS-based navigation tools for drivers today. However, how the guided indoor navigation affects human’s memory of a novel environment has not been well studied. In this paper, we investigate route memory with three types of navigation assistance, that is, 2D map, wearable navigation assistant, and human usher. Twenty participants were asked to remember the route while being guided through a novel indoor environment. Our results show that the participants have similar patterns in remembering visual scenes, even using different types of assistance. These findings support previous work on scene memorability and provide the new insight that scene memorability is not affected by the type of navigation guidance. This may indicate that spatial working memory and visual memory are dissociated. We also show that scenes with navigation information are more memorable than scenes without such information. Finally, we provide some evidence that the location of a scene is linked to its memorability. In general, our findings provide valuable information about indoor scene memorability.     

Seeking a path through the crowd: Robot navigation in unknown dynamic environments with moving obstacles based on an integrated environment representation

We present a novel algorithm for collision free navigation of a non-holonomic robot in unknown complex dynamic environments with moving obstacles. Our approach is based on an integrated representation of the information about the environment which does not require to separate obstacles and approximate their shapes by discs or polygons and is very easy to obtain in practice. Moreover, the proposed algorithm does not require any information on the obstacles’ velocities. Under our navigation algorithm, the robot efficiently seeks a short path through the crowd of moving or steady obstacles. A mathematically rigorous analysis of the proposed approach is provided. The performance of the algorithm is demonstrated via experiments with a real robot and extensive computer simulations.     

Equiangular navigation and guidance of a wheeled mobile robot based on range-only measurements

We consider the problems of a wheeled mobile robot navigation and guidance towards an unknown stationary or maneuvering target using range-only measurements. We propose and study several methods for navigation and guidance termed Equiangular Navigation Guidance (ENG) laws. We give mathematically rigorous analysis of the proposed guidance laws. The performance is confirmed with computer simulations and experiments with ActivMedia Pioneer 3-DX wheeled robots.     

Discrete Orthogonal Decomposition and Variational Fluid Flow Estimation

We exploit the mimetic finite difference method introduced by Hyman and Shashkov to present a framework for estimating vector fields and related scalar fields (divergence, curl) of physical interest from image sequences. Our approach provides a basis for consistent definitions of higher-order differential operators, for the analysis and a novel stability result concerning second-order div-curl regularizers, for novel variational schemes to the estimation of solenoidal (divergence-free) image flows, and to convergent numerical methods in terms of subspace corrections.     

Scene Reconstruction and Robot Navigation Using Dynamic Fields

In this paper, we present an approach to autonomous robot navigation in an unknown environment. We design and integrate algorithms to reconstruct the scene, locate obstacles and do short-term field-based path planning. The scene reconstruction is done using a region matching flow algorithm to recover image deformation and structure from motion to recover depth. Obstacles are located by comparing the surface normal of the known floor with the surface normal of the scene. Our path planning method is based on electric-like fields and uses current densities that can guarantee fields without local minima and maxima which can provide solutions without the need of heuristics that plague the more traditional potential fields approaches. We implemented a modular distributed software platform (FBN) to test this approach and we ran several experiments to verify the performance with very encouraging results.     

Location estimation for indoor autonomous vehicle navigation by omni-directional vision using circular landmarks on ceilings

A novel approach to location estimation by omni-directional vision for autonomous vehicle navigation in indoor environments using circular landmark information is proposed. A circular-shaped landmark is attached on a ceiling and an omni-directional camera is equipped on a vehicle to take upward-looking omni-directional images of the landmark. This way of image taking reduces possible landmark shape occlusion and image noise creation, which come from the existence of nearby objects or humans surrounding the vehicle. It is shown that the perspective shape of the circular landmark in the omni-directional image may be approximated by an ellipse by analytic formulas with good shape-fitting effect and fast computation speed. The parameters of the ellipse are then used for estimating the location of the vehicle with good precision for navigation guidance. Both simulated and real images were tested and good experimental results confirm the feasibility of the proposed approach.     

Generation of accurate integral surfaces in time-dependent vector fields

We present a novel approach for the direct computation of integral surfaces in time-dependent vector fields. As opposed to previous work, which we analyze in detail, our approach is based on a separation of integral surface computation into two stages: surface approximation and generation of a graphical representation. This allows us to overcome several limitations of existing techniques. We first describe an algorithm for surface integration that approximates a series of time lines using iterative refinement and computes a skeleton of the integral surface. In a second step, we generate a well-conditioned triangulation. Our approach allows a highly accurate treatment of very large time-varying vector fields in an efficient, streaming fashion. We examine the properties of the presented methods on several example datasets and perform a numerical study of its correctness and accuracy. Finally, we investigate some visualization aspects of integral surfaces.     

Fuzzy logic techniques for mobile robot obstacle avoidance

This paper is concerned with the problem of reactive navigation for a mobile robot in an unknown clustered environment. We will define reactive navigation as a mapping between sensory data and commands. Building a reactive navigation system means providing such a mapping. It can come from a family of predefined functions (like potential fields methods) or it can be built using ‘universal’ approximators (like neural networks). In this paper, we will consider another ‘universal’ approximator: fuzzy logic. We will explain how to choose the rules using a behaviour decomposition approach. It is possible to build a controller working quite well but the classical problems are still there: oscillations and local minima. Finally, we will conclude that learning is necessary for a robust navigation system and fuzzy logic is an easy way to put some initial knowledge in the system to avoid learning from zero.     

Guided by music: pedestrian and cyclist navigation with route and beacon guidance

Music listening and navigation are both common tasks for mobile device users. In this study, we integrated music listening with a navigation service, allowing users to follow the perceived direction of the music to reach their destination. This navigation interface provided users with two different guidance methods: route guidance and beacon guidance. The user experience of the navigation service was evaluated with pedestrians in a city center and with cyclists in a suburban area. The results show that spatialized music can be used to guide pedestrians and cyclists toward a destination without any prior training, offering a pleasant navigation experience. Both route and beacon guidance were deemed good alternatives, but the preference between them varied from person to person and depended on the situation. Beacon guidance was generally considered to be suitable for familiar surroundings, while route guidance was seen as a better alternative for areas that are unfamiliar or more difficult to navigate.     

Live path: adaptive agent navigation in the interactive virtual world

We present a novel approach to adaptive navigation in the interactive virtual world by using data from the user. Our method constructs automatically a navigation mesh that provides new paths for agents by referencing the user movements. To acquire accurate data samples from all the user data in the interactive world, we use the following techniques: an agent of interest (AOI), a region of interest (ROI) map, and a discretized path graph (DPG). Our method enables adaptive changes to the virtual world over time and provides user-preferred path weights for smart-agent path planning. We have tested the usefulness of our algorithm with several example scenarios from interactive worlds such as video games. In practice, our framework can be applied easily to any type of navigation in an interactive world. In addition, it may prove useful for solving previous pathfinding problems in static navigation planning.     

Interactive comparison of scalar fields based on largest contours with applications to flow visualization

Understanding fluid flow data, especially vortices, is still a challenging task. Sophisticated visualization tools help to gain insight. In this paper, we present a novel approach for the interactive comparison of scalar fields using isosurfaces, and its application to fluid flow datasets. Features in two scalar fields are defined by largest contour segmentation after topological simplification. These features are matched using a volumetric similarity measure based on spatial overlap of individual features. The relationships defined by this similarity measure are ranked and presented in a thumbnail gallery of feature pairs and a graph representation showing all relationships between individual contours. Additionally, linked views of the contour trees are provided to ease navigation. The main render view shows the selected features overlapping each other. Thus, by displaying individual features and their relationships in a structured fashion, we enable exploratory visualization of correlations between similar structures in two scalar fields. We demonstrate the utility of our approach by applying it to a number of complex fluid flow datasets, where the emphasis is put on the comparison of vortex related scalar quantities.     

Real-time landing place assessment in man-made environments

We propose a novel approach to the real-time landing site detection and assessment in unconstrained man-made environments using passive sensors. Because this task must be performed in a few seconds or less, existing methods are often limited to simple local intensity and edge variation cues. By contrast, we show how to efficiently take into account the potential sites’ global shape, which is a critical cue in man-made scenes. Our method relies on a new segmentation algorithm and shape regularity measure to look for polygonal regions in video sequences. In this way, we enforce both temporal consistency and geometric regularity, resulting in very reliable and consistent detections. We demonstrate our approach for the detection of landable sites such as rural fields, building rooftops and runways from color and infrared monocular sequences significantly outperforming the state-of-the-art.     

Exploring feature sets for two-phase biomedical named entity recognition using semi-CRFs

This paper represents a two-phase approach based on semi-Markov conditional random fields model (semi-CRFs) and explores novel feature sets for identifying the entities in text into 5 types: protein, DNA, RNA, cell_line and cell_type. Semi-CRFs put the label to a segment not a single word which is more natural than the other machine learning methods such as conditional random fields model (CRFs). Our approach divides the biomedical named entity recognition task into two sub-tasks: term boundary detection and semantic labeling. At the first phase, term boundary detection sub-task detects the boundary of the entities and classifies the entities into one type C. At the second phase, semantic labeling sub-task labels the entities detected at the first phase the correct entity type. We explore novel feature sets at both phases to improve the performance. To make a comparison, experiments conducted both on CRFs and on semi-CRFs models at each phase. Our experiments carried out on JNLPBA 2004 datasets achieve an F-score of 74.64 % based on semi-CRFs without deep domain knowledge and post-processing algorithms, which outperforms most of the state-of-the-art systems.     

Proportional navigation guidance for robotic interception of moving objects

Two novel navigation‐guidance‐based methods are presented for on‐line‐robotic‐interception of fast‐maneuvering objects. For the first method, an ideal proportional navigation‐guidance (IPNG) technique is used during phase I of the two‐phase robot trajectory planning and control strategy. For the second method, an augmented form of the IPNG (AIPNG) technique is suggested for phase I, when a reliable estimation of the acceleration of the target can be provided to the interceptor. Both techniques are modified to reflect the greater mobility of a robotic manipulator over an airborne interceptor. The convergence analyses of both methods are detailed and compared to that of a conventional moving‐object tracking method. Computer simulations clearly illustrate the effectiveness of the IPNG‐based interception methods over pure tracking‐based techniques proposed in the cited literature. © 2000 John Wiley & Sons, Inc.     

Range-only measurements based target following for wheeled mobile robots

We consider the problem of navigation and guidance of a wheeled mobile robot towards a maneuvering target based on the measurements concerning only the distance from the robot to the target. We propose a sliding mode controller that drives the robot to the predefined distance from the target and makes the robot follow the target at this distance. Mathematically rigorous proof of convergence and stability of the proposed guidance law is presented. Simulation results confirm the applicability and performance of the proposed guidance approach.     

Road detection algorithm for Autonomous Navigation Systems based on dark channel prior and vanishing point in complex road scenes

Vision-based road extraction is essentially important in many fields, such as for intelligent traffic and robot navigation. However, the road detection in urban or ill-structured roads is still very challenging at current stage, and the existing methods often suffer from high computational complexity. This paper reports a novel and efficient method for road detection in challenging scenes. First, the dark channel based image segmentation is proposed to distinguish a rough road region from complex background noise, which is envisioned to reduce the workload of road detection. Furthermore, instead of using the conventional pixel-wise soft voting, a new voting strategy based on the vanishing point and the properties of the segmented regions is proposed to further reduce the computation time of road extraction stage. Finally, the segmented region which has the maximum voting value is selected as the road region. Experimental results demonstrated that the proposed algorithm shows superior performance in different kinds of road scenes. It can remove the interference from pedestrians, vehicles and other obstacles. Our method is about 40 times faster in detection speed, when compared to a recently well-known approach.     

Neural network guidance based on pursuit-evasion games with enhanced performance

This paper addresses a neural network guidance based on pursuit-evasion games, and performance enhancing methods for it. Two-dimensional pursuit-evasion games solved by the gradient-based method are considered. The neural network guidance law employs the range, range rate, line-of-sight rate, and heading error as its input variables. Additional pattern selection methods and a hybrid guidance method are proposed for the sake of the interception performance enhancement. Numerical simulations are accompanied for the verification of the neural network approximation, and of the improved interception performance by the proposed methods. Moreover, all proposed guidance laws are compared with proportional navigation.     

Panorama light‐field imaging

We present a novel approach to recording and computing panorama light fields. In contrast to previous methods that estimate panorama light fields from focal stacks or naive multi‐perspective image stitching, our approach is the first that processes ray entries directly and does not require depth reconstruction or matching of image features. Arbitrarily complex scenes can therefore be captured while preserving correct occlusion boundaries, anisotropic reflections, refractions, and other light effects that go beyond diffuse reflections of Lambertian surfaces.