Author Archives: Juan-antonio Fernández-madrigal

A new variant of A* that is more computationally efficient

September 19, 2018 08:37 ,

Adam Niewola, Leszek Podsedkowski, L* Algorithm—A Linear Computational Complexity Graph Searching Algorithm for Path Planning, Journal of Intelligent & Robotic Systems, September 2018, Volume 91, Issue 3–4, pp 425–444, DOI: 10.1007/s10846-017-0748-6.

The state-of-the-art graph searching algorithm applied to the optimal global path planning problem for mobile robots is the A* algorithm with the heap structured open list. In this paper, we present a novel algorithm, called the L* algorithm, which can be applied to global path planning and is faster than the A* algorithm. The structure of the open list with the use of bidirectional sublists (buckets) ensures the linear computational complexity of the L* algorithm because the nodes in the current bucket can be processed in any sequence and it is not necessary to sort the bucket. Our approach can maintain the optimality and linear computational complexity with the use of the cost expressed by floating-point numbers. The paper presents the requirements of the L* algorithm use and the proof of the admissibility of this algorithm. The experiments confirmed that the L* algorithm is faster than the A* algorithm in various path planning scenarios. We also introduced a method of estimating the execution time of the A* and the L* algorithm. The method was compared with the experimental results.

Posted in: Artificial Intelligence , Tagged: , ,

A summary on reward processing in psychophysiology

September 17, 2018 09:52 ,

Dan Foti, Anna Weinberg, Reward and feedback processing: State of the field, best practices, and future directions, International Journal of Psychophysiology, Volume 132, Part B, 2018, Pages 171-174, DOI: 10.1016/j.ijpsycho.2018.08.006.

There is a long history of studies using event-related potentials (ERPs) to examine how the brain monitors performance. Many initial studies focused on error processing, both internal (i.e., neural activity elicited by error commission) (Falkenstein et al., 1991; Gehring et al., 1993) and external (i.e. neural activity elicited by feedback indicating an unfavorable outcome) (Gehring and Willoughby, 2002; Miltner et al., 1997). A frequent assumption in this line of research has been that correct performance and favorable outcomes served as reference conditions, and that any effects on ERP amplitudes specifically reflected error processing. This starting premise is at odds with the large human and animal neuroscience literatures on reward processing, which focus on the motivated pursuit of said favorable outcomes. In fact, reward and error processing are intrinsically linked, and both undergird effective task performance: the brain is highly sensitive to events that are better or worse than expected in order to continuously modulate behavior in line with task goals (Holroyd and Coles, 2002). In recent years, the ERP literature on feedback processing has broadened to explicitly incorporate reward processing, thereby enriching traditional studies focused on error processing. Specific developments in this regard include an expanded focus on multiple stages of reward processing (e.g., anticipation versus outcome), charting the development of reward processing across the lifespan, and the examination of aberrant sensitivity to reward in psychiatric illnesses. While these advances are highly promising, the general ERP literature on feedback processing continues to be fragmented with regard to terminology, analytic techniques, task designs, and interpretation of findings, ultimately limiting progress in the field.

The overarching goal of this special issue was to carefully examine the state of the art in our current understanding of feedback processing. The aim was to provide an integrative overview that covers multiple theoretical perspectives and methodological approaches. Consideration has been given in this collection of articles to both basic and applied research topics, and throughout the special issue there is an emphasis on providing specific recommendations for study design and the identification of important future research directions. In the remainder of this introductory editorial, we set the stage for these articles by highlighting complementary results and points of intersection across four themes: integrating perspectives on reward and error processing; experimental manipulations, psychometrics, and individual differences.

Posted in: Psycho-physiological bases of engineering , Tagged:

A survey on decision making for multiagent systems, including multirobot systems

September 13, 2018 09:59 ,

Y. Rizk, M. Awad and E. W. Tunstel, Decision Making in Multiagent Systems: A Survey, IEEE Transactions on Cognitive and Developmental Systems, vol. 10, no. 3, pp. 514-529, DOI: 10.1109/TCDS.2018.2840971.

Intelligent transport systems, efficient electric grids, and sensor networks for data collection and analysis are some examples of the multiagent systems (MAS) that cooperate to achieve common goals. Decision making is an integral part of intelligent agents and MAS that will allow such systems to accomplish increasingly complex tasks. In this survey, we investigate state-of-the-art work within the past five years on cooperative MAS decision making models, including Markov decision processes, game theory, swarm intelligence, and graph theoretic models. We survey algorithms that result in optimal and suboptimal policies such as reinforcement learning, dynamic programming, evolutionary computing, and neural networks. We also discuss the application of these models to robotics, wireless sensor networks, cognitive radio networks, intelligent transport systems, and smart electric grids. In addition, we define key terms in the area and discuss remaining challenges that include incorporating big data advancements to decision making, developing autonomous, scalable and computationally efficient algorithms, tackling more complex tasks, and developing standardized evaluation metrics. While recent surveys have been published on this topic, we present a broader discussion of related models and applications.Note to Practitioners:Future smart cities will rely on cooperative MAS that make decisions about what actions to perform that will lead to the completion of their tasks. Decision making models and algorithms have been developed and reported in the literature to generate such sequences of actions. These models are based on a wide variety of principles including human decision making and social animal behavior. In this paper, we survey existing decision making models and algorithms that generate optimal and suboptimal sequences of actions. We also discuss some of the remaining challenges faced by the research community before more effective MAS deployment can be achieved in this age of Internet of Things, robotics, and mobile devices. These challenges include developing more scalable and efficient algorithms, utilizing the abundant sensory data available, tackling more complex tasks, and developing evaluation standards for decision making.

Posted in: Artificial Intelligence , Tagged: , , ,

A new framework for fitting jump models

September 4, 2018 15:23 ,

Alberto Bemporad, Valentina Breschi, Dario Piga, Stephen P. Boyd, Fitting jump models, Automatica, Volume 96, 2018, Pages 11-21, DOI: 10.1016/j.automatica.2018.06.022.

We describe a new framework for fitting jump models to a sequence of data. The key idea is to alternate between minimizing a loss function to fit multiple model parameters, and minimizing a discrete loss function to determine which set of model parameters is active at each data point. The framework is quite general and encompasses popular classes of models, such as hidden Markov models and piecewise affine models. The shape of the chosen loss functions to minimize determines the shape of the resulting jump model.

Posted in: Probability and statistics , Tagged: , ,

Including the dynamics of the environment in robot motion planning (navigation)

September 4, 2018 15:10 ,

María-Teresa Lorente, Eduardo Owen, and Luis Montano, Model-based robocentric planning and navigation for dynamic environments, The International Journal of Robotics Research Vol 37, Issue 8, pp. 867 – 889 DOI: 10.1177/0278364918775520.

This work addresses a new technique of motion planning and navigation for differential-drive robots in dynamic environments. Static and dynamic objects are represented directly on the control space of the robot, where decisions on the best motion are made. A new model representing the dynamism and the prediction of the future behavior of the environment is defined, the dynamic object velocity space (DOVS). A formal definition of this model is provided, establishing the properties for its characterization. An analysis of its complexity, compared with other methods, is performed. The model contains information about the future behavior of obstacles, mapped on the robot control space. It allows planning of near-time-optimal safe motions within the visibility space horizon, not only for the current sampling period. Navigation strategies are developed based on the identification of situations in the model. The planned strategy is applied and updated for each sampling time, adapting to changes occurring in the scenario. The technique is evaluated in randomly generated simulated scenarios, based on metrics defined using safety and time-to-goal criteria. An evaluation in real-world experiments is also presented.

Posted in: Robot motion planning , Tagged:

A probabilistically rigurous formulation of the estimation of grid maps in dynamic scenarios, and a nice review and state-of-the-art of grid maps, both for static and dynamic scenarios

September 4, 2018 15:08 ,

Dominik Nuss, Stephan Reuter, Markus Thom, Ting Yuan, Gunther Krehl, Michael Maile, Axel Gern, and Klaus Dietmayer, A random finite set approach for dynamic occupancy grid maps with real-time application, The International Journal of Robotics Research
Vol 37, Issue 8, pp. 841 – 866, DOI: 10.1177/0278364918775523.

Grid mapping is a well-established approach for environment perception in robotic and automotive applications. Early work suggests estimating the occupancy state of each grid cell in a robot’s environment using a Bayesian filter to recursively combine new measurements with the current posterior state estimate of each grid cell. This filter is often referred to as binary Bayes filter. A basic assumption of classical occupancy grid maps is a stationary environment. Recent publications describe bottom-up approaches using particles to represent the dynamic state of a grid cell and outline prediction-update recursions in a heuristic manner. This paper defines the state of multiple grid cells as a random finite set, which allows to model the environment as a stochastic, dynamic system with multiple obstacles, observed by a stochastic measurement system. It motivates an original filter called the probability hypothesis density / multi-instance Bernoulli (PHD/MIB) filter in a top-down manner. The paper presents a real-time application serving as a fusion layer for laser and radar sensor data and describes in detail a highly efficient parallel particle filter implementation. A quantitative evaluation shows that parameters of the stochastic process model affect the filter results as theoretically expected and that appropriate process and observation models provide consistent state estimation results.

Posted in: Mobile robot mapping , Tagged: , ,

Interpreting time series patterns through reasoning

September 3, 2018 16:31 ,

T. Teijeiro, P. Félix, On the adoption of abductive reasoning for time series interpretation, Artificial Intelligence, Volume 262, 2018, Pages 163-188, DOI: 10.1016/j.artint.2018.06.005.

Time series interpretation aims to provide an explanation of what is observed in terms of its underlying processes. The present work is based on the assumption that the common classification-based approaches to time series interpretation suffer from a set of inherent weaknesses, whose ultimate cause lies in the monotonic nature of the deductive reasoning paradigm. In this document we propose a new approach to this problem, based on the initial hypothesis that abductive reasoning properly accounts for the human ability to identify and characterize the patterns appearing in a time series. The result of this interpretation is a set of conjectures in the form of observations, organized into an abstraction hierarchy and explaining what has been observed. A knowledge-based framework and a set of algorithms for the interpretation task are provided, implementing a hypothesize-and-test cycle guided by an attentional mechanism. As a representative application domain, interpretation of the electrocardiogram allows us to highlight the strengths of the proposed approach in comparison with traditional classification-based approaches.

Posted in: Artificial Intelligence , Tagged: ,

Interesting review of time delay measurement in one-way messages in networks at the application level

September 3, 2018 16:24 ,

P. Ferrari, A. Flammini, E. Sisinni, S. Rinaldi, D. Brandão and M. S. Rocha, Delay Estimation of Industrial IoT Applications Based on Messaging Protocols, IEEE Transactions on Instrumentation and Measurement, vol. 67, no. 9, pp. 2188-2199, DOI: 10.1109/TIM.2018.2813798.

Information and operational technologies merge into the so-called industrial Internet of Things, which is one of the basic pillars of the Industry 4.0 paradigm. Roughly speaking, yet-to-come services will be offered in the automation scenario by industrial devices having an internet connection for sharing data in the cloud. Currently, most efforts are in the development of protocols able to ensure horizontal interoperability among heterogeneous applications. Consequently, poor attention is devoted to time-related performance. In this paper, a new, full software, platform-independent approach is proposed for experimentally evaluating the delay in transferring information across local and intercontinental routes by applications leveraging on messaging middleware. The application is realized using the node-RED web-based framework, due to its availability on different platforms; the widely accepted message queue telemetry transport protocol has been chosen thanks to its low overhead and complexity. For sake of completeness, five different, private and public, brokers are used. The adopted industrial-grade hardware, complemented by global positioning system time reference, permits an overall synchronization and timestamping accuracy of a few milliseconds. The vast measurement campaign highlighted that, generally, quality of service (QoS) type 1 offers low end-to-end delay (average value less than 0.5 s) with reduced variability (0.1 s). However, the maximum end-to-end one-way delay ranges from 1 s for QoS 0 to less than 1.5 s for fully acknowledged QoS 2.

Posted in: Communication networks , Tagged: , ,

Considering the robot and all the intermmediate objects that participate in the manipulation of another object as a MDP

September 3, 2018 15:58 ,

Yilun Zhou, Benjamin Burchfiel, George Konidaris, Representing, learning, and controlling complex object interactions, Autonomous Robots, Volume 42, Issue 7, pp 1355–1367, DOI: 10.1007/s1051.

We present a framework for representing scenarios with complex object interactions, where a robot cannot directly interact with the object it wishes to control and must instead influence it via intermediate objects. For instance, a robot learning to drive a car can only change the car’s pose indirectly via the steering wheel, and must represent and reason about the relationship between its own grippers and the steering wheel, and the relationship between the steering wheel and the car. We formalize these interactions as chains and graphs of Markov decision processes (MDPs) and show how such models can be learned from data. We also consider how they can be controlled given known or learned dynamics. We show that our complex model can be collapsed into a single MDP and solved to find an optimal policy for the combined system. Since the resulting MDP may be very large, we also introduce a planning algorithm that efficiently produces a potentially suboptimal policy. We apply these models to two systems in which a robot uses learning from demonstration to achieve indirect control: playing a computer game using a joystick, and using a hot water dispenser to heat a cup of water.

Posted in: Robot task planning , Tagged: ,

Loop closure detection by optimization of finite sets of images that correspond to each place

September 3, 2018 15:53 ,

Han, F., Wang, H., Huang, G. et al, Sequence-based sparse optimization methods for long-term loop closure detection in visual SLAM, Autonomous Robots, Volume 42, Issue 7, pp 1323–1335, DOI: 10.1007/s1051.

Loop closure detection is one of the most important module in Simultaneously Localization and Mapping (SLAM) because it enables to find the global topology among different places. A loop closure is detected when the current place is recognized to match the previous visited places. When the SLAM is executed throughout a long-term period, there will be additional challenges for the loop closure detection. The illumination, weather, and vegetation conditions can often change significantly during the life-long SLAM, resulting in the critical strong perceptual aliasing and appearance variation problems in loop closure detection. In order to address this problem, we propose a new Robust Multimodal Sequence-based (ROMS) method for robust loop closure detection in long-term visual SLAM. A sequence of images is used as the representation of places in our ROMS method, where each image in the sequence is encoded by multiple feature modalites so that different places can be recognized discriminatively. We formulate the robust place recognition problem as a convex optimization problem with structured sparsity regularization due to the fact that only a small set of template places can match the query place. In addition, we also develop a new algorithm to solve the formulated optimization problem efficiently, which guarantees to converge to the global optima theoretically. Our ROMS method is evaluated through extensive experiments on three large-scale benchmark datasets, which record scenes ranging from different times of the day, months, and seasons. Experimental results demonstrate that our ROMS method outperforms the existing loop closure detection methods in long-term SLAM, and achieves the state-of-the-art performance.

Posted in: Mobile robot SLAM , Tagged: