Author Archives: Juan-antonio Fernández-madrigal

A novel fast algorithm for clock synchronization in a wireless network, with a nice introduction but assuming negligible communication times and thus not directly applicable in teleoperation

April 8, 2018 09:39 ,

Kan Xie, Qianqian Cai, Minyue Fu, A fast clock synchronization algorithm for wireless sensor networks, Automatica, Volume 92, 2018, Pages 133-142, DOI: 10.1016/j.automatica.2018.03.004.

This paper proposes a novel clock synchronization algorithm for wireless sensor networks (WSNs). The algorithm is derived using a fast finite-time average consensus idea, and is fully distributed, meaning that each node relies only on its local clock readings and reading announcements from its neighbours. For networks with an acyclic graph, the algorithm converges in only d iterations for clock rate synchronization and another d iterations for clock offset synchronization, where d is the graph diameter. The algorithm enjoys low computational and communicational complexities and robustness against transmission adversaries. Each node can execute the algorithm asynchronously without the need for global coordination. Due to its fast convergence, the algorithm is most suitable for large-scale WSNs. For WSNs with a cyclic graph, a fast distributed depth-first-search (DFS) algorithm can be applied first to form a spanning tree before applying the proposed synchronization algorithm.

Posted in: Communication networks , Tagged: ,

POMDPs aware of the data association problem

March 29, 2018 09:32 ,

Shashank Pathak, Antony Thomas, and Vadim Indelman, A unified framework for data association aware robust belief space planning and perception, The International Journal of Robotics Research Vol 37, Issue 2-3, pp. 287 – 315, DOI: 10.1177/0278364918759606.

We develop a belief space planning approach that advances the state of the art by incorporating reasoning about data association within planning, while considering additional sources of uncertainty. Existing belief space planning approaches typically assume that data association is given and perfect, an assumption that can be harder to justify during operation in the presence of localization uncertainty, or in ambiguous and perceptually aliased environments. By contrast, our data association aware belief space planning (DA-BSP) approach explicitly reasons about data association within belief evolution owing to candidate actions, and as such can better accommodate these challenging real-world scenarios. In particular, we show that, owing to perceptual aliasing, a posterior belief can become a mixture of probability distribution functions and design cost functions, which measure the expected level of ambiguity and posterior uncertainty given candidate action. Furthermore, we also investigate more challenging situations, such as when prior belief is multimodal and when data association aware planning is performed over several look-ahead steps. Our framework models the belief as a Gaussian mixture model. Another unique aspect of this approach is that the number of components of this Gaussian mixture model can increase as well as decrease, thereby reflecting reality more accurately. Using these and standard costs (e.g. control penalty, distance to goal) within the objective function yields a general framework that reliably represents action impact and, in particular, is capable of active disambiguation. Our approach is thus applicable to both robust perception in a passive setting with data given a priori and in an active setting, such as in autonomous navigation in perceptually aliased environments. We demonstrate key aspects of DA-BSP in a theoretical example, in a Gazebo-based realistic simulation, and also on the real robotic platform using a Pioneer robot in an office environment.

Posted in: Probability and statistics, Robot task planning , Tagged: ,

Using EKF estimation in a PI controller for improving its performance under noise

March 29, 2018 09:29 ,

Y. Zhou, Q. Zhang, H. Wang, P. Zhou and T. Chai, EKF-Based Enhanced Performance Controller Design for Nonlinear Stochastic Systems, IEEE Transactions on Automatic Control, vol. 63, no. 4, pp. 1155-1162, DOI: 10.1109/TAC.2017.2742661.

In this paper, a novel control algorithm is presented to enhance the performance of the tracking property for a class of nonlinear and dynamic stochastic systems subjected to non-Gaussian noises. Although the existing standard PI controller can be used to obtain the basic tracking of the systems, the desired tracking performance of the stochastic systems is difficult to achieve due to the random noises. To improve the tracking performance, an enhanced performance loop is constructed using the EKF-based state estimates without changing the existing closed loop with a PI controller. Meanwhile, the gain of the enhanced performance loop can be obtained based upon the entropy optimization of the tracking error. In addition, the stability of the closed loop system is analyzed in the mean-square sense. The simulation results are given to illustrate the effectiveness of the proposed control algorithm.

Posted in: Bayesian filtering, Control Engineering , Tagged: ,

Optimal routing in communication networks with probabilistic models of delays that are acquired on-line

March 29, 2018 09:26 ,

M. S. Talebi, Z. Zou, R. Combes, A. Proutiere and M. Johansson, Stochastic Online Shortest Path Routing: The Value of Feedback, IEEE Transactions on Automatic Control, vol. 63, no. 4, pp. 915-930, DOI: 10.1109/TAC.2017.2747409.

This paper studies online shortest path routing over multihop networks. Link costs or delays are time varying and modeled by independent and identically distributed random processes, whose parameters are initially unknown. The parameters, and hence the optimal path, can only be estimated by routing packets through the network and observing the realized delays. Our aim is to find a routing policy that minimizes the regret (the cumulative difference of expected delay) between the path chosen by the policy and the unknown optimal path. We formulate the problem as a combinatorial bandit optimization problem and consider several scenarios that differ in where routing decisions are made and in the information available when making the decisions. For each scenario, we derive a tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. Three algorithms, with a tradeoff between computational complexity and performance, are proposed. The regret upper bounds of these algorithms improve over those of the existing algorithms. We also assess numerically the performance of the proposed algorithms and compare it to that of existing algorithms.

Posted in: Communication networks , Tagged: ,

Mapping the wifi signal for robot localization both precisely and accurately through a complex model of the signal

March 28, 2018 09:22 ,

Renato Miyagusuku, Atsushi Yamashita, Hajime Asama, Precise and accurate wireless signal strength mappings using Gaussian processes and path loss models, Robotics and Autonomous Systems, Volume 103, 2018, Pages 134-150, DOI: 10.1016/j.robot.2018.02.011.

In this work, we present a new modeling approach that generates precise (low variance) and accurate (low mean error) wireless signal strength mappings. In robot localization, these mappings are used to compute the likelihood of locations conditioned to new sensor measurements. Therefore, both mean and variance predictions are required. Gaussian processes have been successfully used for learning highly accurate mappings. However, they generalize poorly at locations far from their training inputs, making those predictions have high variance (low precision). In this work, we address this issue by incorporating path loss models, which are parametric functions that although lacking in accuracy, generalize well. Path loss models are used together with Gaussian processes to compute mean predictions and most importantly, to bound Gaussian processes’ predicted variances. Through extensive testing done with our open source framework, we demonstrate the ability of our approach to generating precise and accurate mappings, and the increased localization accuracy of Monte Carlo localization algorithms when using them; with all our datasets and software been made readily available online for the community.

Posted in: Communication networks, Mobile Robot Localization , Tagged: ,

A novel motion planning algorithm for robot navigation taking into account the robot kinematic constraints and shape

March 28, 2018 09:18 ,

Muhannad Mujahed, Dirk Fischer, Bärbel Mertsching, Admissible gap navigation: A new collision avoidance approach, Robotics and Autonomous Systems,
Volume 103, 2018, Pages 93-110, DOI: 10.1016/j.robot.2018.02.008.

This paper proposes a new concept, the Admissible Gap (AG), for reactive collision avoidance. A gap is called admissible if it is possible to find a collision-free motion control that guides a robot through it, while respecting the vehicle constraints. By utilizing this concept, a new navigation approach was developed, achieving an outstanding performance in unknown dense environments. Unlike the widely used gap-based methods, our approach directly accounts for the exact shape and kinematics, rather than finding a direction solution and turning it later into a collision-free admissible motion. The key idea is to analyze the structure of obstacles and virtually locate an admissible gap, once traversed, the robot makes progress towards the goal. For this purpose, we introduce a strategy of traversing gaps that respect the kinematic constraints and provides a compromise between path length and motion safety. We also propose a new methodology for extracting gaps that eliminates useless ones, thus reducing oscillations. Experimental results along with performance evaluation demonstrate the outstanding behavior of the proposed AG approach. Furthermore, a comparison with existing state-of-the-art methods shows that the AG approach achieves the best results in terms of efficiency, robustness, safety, and smoothness.

Posted in: Robot motion planning , Tagged: ,

A robot designed to integrate socially with a group of chickens and study their behaviour

March 28, 2018 09:10 ,

A. Gribovskiy, J. Halloy, J.L. Deneubourg, F. Mondada, Designing a socially integrated mobile robot for ethological research, Robotics and Autonomous Systems, Volume 103, 2018, Pages 42-55, DOI: 10.1016/j.robot.2018.02.003.

A robot introduced into an animal group, accepted by the animals as conspecifics, and capable of interacting with them is an efficient tool for ethological research, particularly in studies of collective and social behaviour. In this paper, we present the implementation of an autonomous mobile robot developed by the authors to study group behaviour of chicks of the domestic chicken (Gallus gallus domesticus). We discuss the design of the robot and of the experimental framework that we built to run animal–robot experiments. The robot design was experimentally validated, we demonstrated that the robot can be socially integrated into animal groups. The designed system extends the current state of the art in the field of animal–robot interaction in general and the birds study in particular by combining such advantages as (1) the robot being a part of the group, (2) the possibility of mixed multi-robot, multi-animal groups, and (3) close-loop control of robots. It opens new opportunities in the study of behaviour in domestic fowl by using mobile robots; being socially integrated into the animal group, robots can profit from the positive feedback mechanism that plays key roles in animal collective behaviour. They have potential applications in various domains, from pure scientific research to applied areas such as control and ensuring welfare of poultry.

Posted in: Robot applications , Tagged: ,

A robotic wheelchair navigation algorithm that plans paths taking into account the discomfort of the user

March 28, 2018 09:07 ,

Yoichi Morales, Atsushi Watanabe, Florent Ferreri, Jani Even, Kazuhiro Shinozawa, Norihiro Hagita, Passenger discomfort map for autonomous navigation in a robotic wheelchair, Robotics and Autonomous Systems, Volume 103, 2018, Pages 13-26, DOI: 10.1016/j.robot.2018.02.002.

This work presents a navigational approach that takes into consideration the perception of comfort by a human passenger. Comfort is the state of being at ease and free from stress; thus, comfortable navigation is a ride that, in addition to being safe, is perceived by the passenger as being free from anxiety and stress. This study considers how to compute passenger comfortable paths. To compute such paths, passenger discomfort is studied in locations with good visibility and those with no visibility. In locations with good visibility, passenger preference to ride in the road is studied. For locations with non-visible areas, the relationship between passenger visibility and discomfort is studied. Autonomous-navigation experiments are performed to build a map of human discomfort that is used to compute global paths. A path planner is proposed that minimizes a three-variable cost function: location discomfort cost, area visibility cost, and path length cost. Planner parameters are calibrated toward a composite trajectory histogram built with data taken from participant self-driving trajectories. Finally, autonomous navigation experiments with 30 participants show that the proposed approach is rated as more comfortable than the state-of-the-art shortest planner approach.

Posted in: Robot motion planning , Tagged: ,

A novel method of mathematical compression of the value function for polynomial (in the state) time complexity of value iteration / policy iteration

March 27, 2018 09:01 ,

Alex Gorodetsky, Sertac Karaman, and Youssef Marzouk, High-dimensional stochastic optimal control using continuous tensor decompositions, The International Journal of Robotics Research Vol 37, Issue 2-3, pp. 340 – 377, DOI: 10.1177/0278364917753994.

Motion planning and control problems are embedded and essential in almost all robotics applications. These problems are often formulated as stochastic optimal control problems and solved using dynamic programming algorithms. Unfortunately, most existing algorithms that guarantee convergence to optimal solutions suffer from the curse of dimensionality: the run time of the algorithm grows exponentially with the dimension of the state space of the system. We propose novel dynamic programming algorithms that alleviate the curse of dimensionality in problems that exhibit certain low-rank structure. The proposed algorithms are based on continuous tensor decompositions recently developed by the authors. Essentially, the algorithms represent high-dimensional functions (e.g. the value function) in a compressed format, and directly perform dynamic programming computations (e.g. value iteration, policy iteration) in this format. Under certain technical assumptions, the new algorithms guarantee convergence towards optimal solutions with arbitrary precision. Furthermore, the run times of the new algorithms scale polynomially with the state dimension and polynomially with the ranks of the value function. This approach realizes substantial computational savings in “compressible” problem instances, where value functions admit low-rank approximations. We demonstrate the new algorithms in a wide range of problems, including a simulated six-dimensional agile quadcopter maneuvering example and a seven-dimensional aircraft perching example. In some of these examples, we estimate computational savings of up to 10 orders of magnitude over standard value iteration algorithms. We further demonstrate the algorithms running in real time on board a quadcopter during a flight experiment under motion capture.

Posted in: Probability and statistics, Robot motion planning , Tagged: , , , ,

A microprocessor designed for real-time predictability and short WCETs

March 26, 2018 08:58 ,

Schoeberl, M., Puffitsch, W., Hepp, S. et al, Patmos: a time-predictable microprocessor, Real-Time Syst (2018) 54: 389, DOI: 10.1007/s11241-018-9300-4.

Current processors provide high average-case performance, as they are optimized for general purpose computing. However, those optimizations often lead to a high worst-case execution time (WCET). WCET analysis tools model the architectural features that increase average-case performance. To keep analysis complexity manageable, those models need to abstract from implementation details. This abstraction further increases the WCET bound. This paper presents a way out of this dilemma: a processor designed for real-time systems. We design and optimize a processor, called Patmos, for low WCET bounds rather than for high average-case performance. Patmos is a dual-issue, statically scheduled RISC processor. A method cache serves as the cache for the instructions and a split cache organization simplifies the WCET analysis of the data cache. To fill the dual-issue pipeline with enough useful instructions, Patmos relies on a customized compiler. The compiler also plays a central role in optimizing the application for the WCET instead of average-case performance.

Posted in: Electronics, Real-Time Systems , Tagged: , ,