This paper presents a robust solution to the mobile robotics data association problem based on solving the maximum clique problem (MCP) in a typically sparse correspondence graph, which contains compatibility information between pairs of observations and landmarks. Bit sparse optimizations are designed and implemented in a new algorithm BBMCS, which reduces computation and memory requirements of a leading general purpose maximum clique solver, to make it possibly the best exact sparse MCP algorithm currently found in the literature. BBMCS is reported to achieve very good results in terms of robustness with few assumptions on noise and visibility, while managing very reasonable computation time and memory usage even for complex large data association problems.

This paper presents the structure and operation principles of an emotional model. It is a dynamic state-space model where state variables represent the emotional state. Model matrices are time variant. A method based on fuzzy inference systems is developed to calculate the matrix coefficients at each time step. The simulation results of the guide robot case study are presented.

This paper presents a feature based 3D mapping approach with regard to obtaining compact models of semi-structured environments such as partially destroyed buildings where mobile robots are to carry out rescue activities. To gather the 3D data, we use a laser scanner, employing a nodding data acquisition system mounted on both real and simulated robots. Our segmentation algorithm comes up from the integration of computer vision techniques, allowing for a fast separation of points corresponding to different, not necessarily planar, surfaces. The subsequent extraction of geometrical features out of each region's points is done by means of least-squares fitting. A Maximum Incremental Probability algorithm formulated upon the Extended Kalman Filter provides 6D localization and produces a map of planar patches with a convex-hull based representation. Scenarios from the Unified System for Automation and Robot Simulation (USARSim), including world models from past RoboCup Rescue editions' arenas, have been utilized to conduct some of our experiments.

This paper describes a simultaneous localization and mapping (SLAM) algorithm for use in unstructured environments that is effective regardless of the geometric complexity of the environment. Features are described using B-splines as modeling tool, and the set of control points defining their shape is used to form a complete and compact description of the environment, thus making it feasible to use an extended Kalman-filter (EKF) based SLAM algorithm. This method is the first known EKF-SLAM implementation capable of describing general free-form features in a parametric manner. Efficient strategies for computing the relevant Jacobians, perform data association, initialization, and map enlargement are presented. The algorithms are evaluated for accuracy and consistency using computer simulations, and for effectiveness using experimental data gathered from different real environments.

This paper presents two new exact general purpose bit-parallel algorithms (BB-SAT and BBP-SAT) for the Boolean satisfiability problem (SAT). Based on the authors' recent successful bit-parallel algorithm for the maximum clique problem, the SAT formula is first reduced to a directed graph which is then bit encoded. As a result, search traverses a bit vector graph space. At present the encoding allows for an efficient bitwise computation of graph state transitions as well as unit clause and pure literal evaluation. Experiments carried out on a number of DIMACS instances are highly encouraging since BBP-SAT is already reasonably competitive employing just basic DPLL tactics with minor refinements. BBP-SAT is a fresh approach in an otherwise mature domain. Further additional bit encoded knowledge of the more recent successful SAT algorithms (e.g. bit parallel heuristic variable selection) should make BBP-SAT a competitive general purpose solver.

Recently, a novel solution to the Simultaneous Localization and Map building (SLAM) problem for complex indoor environments was presented, using a set of splines for describing the geometries detected by a laser range finder mounted on a mobile platform. In this paper, a method for exploiting the geometric information underlying in these maps in the data association process is described. The proposed approach uses graphs of relations between simple features extracted from the environment, and a bit encoded implementation for obtaining a maximum clique that relates observations with previously visited areas. This information is used to update the relative positions of a collage of submaps of limited size.

This paper presents a technique to improve the data association in the iterative closest point based scan matching. The method is based on a distance-filter constructed on the basis of an analysis of the set of solutions produced by the associations in the sensor configuration space. This leads to a robust strategy to filter all the associations that do not explain the principal motion of the scan (due to noise in the sensor, large odometry errors, spurious, occlusions or dynamic features for example). The experimental results suggest that the improvement of the data association leads to more robust and faster methods in the presence of wrong correspondences.

It is the authors' belief that the ability of processors to compute bit parallel operations should have a right to exist as an optimization discipline, rather than a state-of- the-art technique. This paper is a step forward in this direction analysing a number of key issues related to bit model design and implementation of search problems. Building efficient search algorithms optimized at bit level is a difficult task It requires not only a good implementation but also an adequate model so as to make bitwise operations meaningful, and only by addressing design and implementation globally an improvement in efficiency can be obtained. On the other hand, we have proved in this paper that the improvement can conceivably be exponential on the size of the CPU register for problems in NP. This global approach has been used to implement the fastest complete algorithm, to the best of our knowledge, for the maximum clique problem, an important NP-hard combinatorial problem from the graph domain. Our solver clearly outperforms other existing algorithms for hard instances, in some cases by nearly an order of magnitude.

The solution to the simultaneous localization and mapping (SLAM) problem using an extended Kalman filter (EKF) is the most extended despite the inconsistency of its estimation, a problem that has been largely avoided in the literature. We review current existing approaches and present novel solutions to this problem that let us to build large monolithic feature based maps of indoor environments

This paper shows a way to speed up search by using an encoding at bit level to model a particular domain. A bitboard is an unsigned integer whose bits have been given an interpretation in the world of discourse. In models encoded in such a way, states will be described internally as a set of bitboard tuples, whilst operators which allow for transitions between states are essentially bitwise operations over elements belonging to that set. Given a 64-bit processor word, for each transition it would be theoretically possible to reach another state 64 times faster than with a normal encoding, fast transitions being one of the main issues for efficient search algorithms. We have analysed some other key issues related to efficient bitboard model design and formalised the concepts of well formed heuristics and bitboard guides. We have used this approach to solve instances of the maximum clique problem thus increasing the performance of one of the fastest algorithms known in the domain for optimal search

Guido is a healthcare robot that serves as support and navigation aid for the frail and visually impaired. The previous assistive navigation software has been replaced by a full map based control, including real time feature based map building (SLAM) and pose tracking (both using an EKF), and path planning and collision avoidance. Real experiments have been carried out, both in the lab and in the hospital, with great success, showing a high improvement in the ease of use and convenience of the system. The map building and editing tools have proved to be extremely useful, enabling the system to be installed in a new environment in just minutes.

This paper presents an implementation of the local maps fusion concept for the simultaneous localization and mapping (SLAM) problem within the extended Kalman filter (EKF) framework. Several problems never addressed before, arise while implementing the solution for indoor environments, and are successfully solved to obtain maps of quite large real indoor environments with more than one robot in real time.

Presents the first approach towards the main goal of developing a completely autonomous robot that serves as a local and remote guide at a trade fair. Innovative solutions are provided to solve several problems found in this environment. Reactive-perceptual behaviors are executed to provide motion while a low level controller avoids collisions. A virtual corridor map, simulated perception, and an extended Kalman filter for localization, are used to overcome the lack of perception. Voice synthesizing is proved to be an effective aid for navigation, as well as for the overall success and acceptance of the system. A Denning Mrv4 robot called Blacky was used to carry out experiments in actual environments on three occasions, and the obtained conclusions sound promising for future research.