Experience Learning From Basic Patterns for Efficient Robot Navigation in Indoor Environments

In this paper we propose a machine learning technique for real-time robot path planning for an autonomous robot in a planar environment with obstacles where the robot possess no a priori map of its environment. Our main insight in this paper is that a robot’s path planning times can be significantly reduced if it can refer to previous maneuvers it used to avoid obstacles during earlier missions, and adapt that information to avoid obstacles during its current navigation. We propose an online path planning algorithm called LearnerRRT that utilizes a pattern matching technique called Sample Consensus Initial Alignment (SAC-IA) in combination with an experience-based learning technique to adapt obstacle boundary patterns encountered in previous environments to the current scenario followed by corresponding adaptations in the obstacle-avoidance paths. Our proposed algorithm LearnerRRT works as a learning-based reactive path planning technique which enables robots to improve their overall path planning performance by locally improving maneuvers around commonly encountered obstacle patterns by accessing previously accumulated environmental information. We have conducted several experiments in simulations and hardware to verify the performance of the LearnerRRT algorithm and compared it with a state-of-the-art sampling-based planner. LearnerRRT on average takes approximately 10% of the planning time and 14% of the total time taken by the sampling-based planner to solve the same navigation task based on simulation results and takes only 33% of the planning time, 46% of total time and 95% of total distance compared to the sampling-based planner based on our hardware results.     

<Emphasis Type="Italic">κ</Emphasis>-<Emphasis Type="Italic">PMP</Emphasis>: Enhancing Physics-based Motion Planners with Knowledge-Based Reasoning

Physics-based motion planning is a challenging task, since it requires the computation of the robot motions while allowing possible interactions with (some of) the obstacles in the environment. Kinodynamic motion planners equipped with a dynamic engine acting as state propagator are usually used for that purpose. The difficulties arise in the setting of the adequate forces for the interactions and because these interactions may change the pose of the manipulatable obstacles, thus either facilitating or preventing the finding of a solution path. The use of knowledge can alleviate the stated difficulties. This paper proposes the use of an enhanced state propagator composed of a dynamic engine and a low-level geometric reasoning process that is used to determine how to interact with the objects, i.e. from where and with which forces. The proposal, called κ-PMP can be used with any kinodynamic planner, thus giving rise to e.g. κ-RRT. The approach also includes a preprocessing step that infers from a semantic abstract knowledge described in terms of an ontology the manipulation knowledge required by the reasoning process. The proposed approach has been validated with several examples involving an holonomic mobile robot, a robot with differential constraints and a serial manipulator, and benchmarked using several state-of-the art kinodynamic planners. The results showed a significant difference in the power consumption with respect to simple physics-based planning, an improvement in the success rate and in the quality of the solution paths.     

Guaranteeing Response Times for Aperiodic Tasks in Global Multiprocessor Scheduling

We provide a constant time schedulability test for an on-line multiprocessor server handling aperiodic tasks. Dhall's effect is avoided by dividing the tasks in two priority classes based on task utilization: heavy and light. We prove that if the load on the multiprocessor server stays below U _threshold = 3 ? √7 ≈ 35.425%, the server can accept an incoming aperiodic task and guarantee that the deadlines of all accepted tasks will be met. The same number 35.425% is also a threshold for a task to be characterized as heavy.The bound U _threshold = 3 ? √7≈ 35.425% is easy-to-use, but not sharp if we know the number of processors in the multiprocessor system. Assuming the server to be equipped with m processors, we calculate a formula for the sharp bound U _threshold (m), which converges to U _threshold from above as m → ∞.The results are based on a utilization function u(x) = 2(1 ? x)/(2 + √2+2x). By using this function, the performance of the multiprocessor server can in some cases be improved beyond U _threshold(m) by paying the extra overhead of monitoring the individual utilization of the current tasks.     

Exploiting submodular value functions for scaling up active perception

In active perception tasks, an agent aims to select sensory actions that reduce its uncertainty about one or more hidden variables. For example, a mobile robot takes sensory actions to efficiently navigate in a new environment. While partially observable Markov decision processes (POMDPs) provide a natural model for such problems, reward functions that directly penalize uncertainty in the agent’s belief can remove the piecewise-linear and convex (PWLC) property of the value function required by most POMDP planners. Furthermore, as the number of sensors available to the agent grows, the computational cost of POMDP planning grows exponentially with it, making POMDP planning infeasible with traditional methods. In this article, we address a twofold challenge of modeling and planning for active perception tasks. We analyze \(\rho \)POMDP and POMDP-IR, two frameworks for modeling active perception tasks, that restore the PWLC property of the value function. We show the mathematical equivalence of these two frameworks by showing that given a \(\rho \)POMDP along with a policy, they can be reduced to a POMDP-IR and an equivalent policy (and vice-versa). We prove that the value function for the given \(\rho \)POMDP (and the given policy) and the reduced POMDP-IR (and the reduced policy) is the same. To efficiently plan for active perception tasks, we identify and exploit the independence properties of POMDP-IR to reduce the computational cost of solving POMDP-IR (and \(\rho \)POMDP). We propose greedy point-based value iteration (PBVI), a new POMDP planning method that uses greedy maximization to greatly improve scalability in the action space of an active perception POMDP. Furthermore, we show that, under certain conditions, including submodularity, the value function computed using greedy PBVI is guaranteed to have bounded error with respect to the optimal value function. We establish the conditions under which the value function of an active perception POMDP is guaranteed to be submodular. Finally, we present a detailed empirical analysis on a dataset collected from a multi-camera tracking system employed in a shopping mall. Our method achieves similar performance to existing methods but at a fraction of the computational cost leading to better scalability for solving active perception tasks.     

Challenges in online collaboration: effects of scripting shared task perceptions

Difficulties with planning, such as negotiating task understandings and goals, can have a profound effect on regulation and task performance when students work collaboratively (Miller and Hadwin, Computers in Human Behaviour, 52, 573-588, 2015a). Despite planning being a common challenge, teams often fail to identify strategies for addressing those challenges successfully. The purpose of this study was to examine the effect of team planning support in the form of awareness visualizations (quantified, nominal, and no visualization of individual planning perceptions summarized across group members) on the challenges students face during collaboration, and the ways they report regulating in the face of those challenges. Findings revealed differences across conditions. Individuals in the no visualization condition (a) rated planning as more problematic, and (b) were likely to encounter doing the task, checking progress, and group work challenges when they encounter planning challenges, (c) reported more time and planning main challenges compared to doing the task and group work challenges, and (d) reported that planning strategies (adopted as a team) were most effective for addressing planning challenges, followed by teamwork strategies which were less effective. In contrast, individuals belonging to groups who received one of the two visualizations (a) reported that both planning and teamwork strategies to be equally effective for addressing planning challenges, and (b) reported higher levels of success with their strategies than groups without a visualization support. Findings attest to the importance of supporting group planning with planning visualizations.     

Adaptive Behaviors in Autonomous Navigation with Collision Avoidance and Bounded Velocity of an Omnidirectional Mobile Robot

Integration of Control Theory and Genetic Programming paradigm toward development a family of controllers is addressed in this paper. These controllers are applied for autonomous navigation with collision avoidance and bounded velocity of an omnidirectional mobile robot. We introduce the concepts of natural and adaptive behaviors to relate each control objective with a desired behavior for the mobile robot. Natural behaviors lead the system to fulfill a task inherently. In this work, the motion of the mobile robot to achieve desired position, ensured by applying a Control-Theory-based controller, defines the natural behavior. The adaptive behavior, learned through Genetic-Programming, fits the robot motion in order to avoid collision with an obstacle while fulfilling velocity constraints. Hence, the behavior of the mobile robot is the addition of the natural and the adaptive behaviors. Our proposed methodology achieves the discovery of 9402 behaviors without collisions where asymptotic convergence to desired goal position is demonstrated by Lyapunov stability theory. Effectiveness of proposed framework is illustrated through a comparison between experiments and numerical simulations for a real mobile robot.     

A Learning-based Multi-RRT Approach for Robot Path Planning in Narrow Passages

As an important class of sampling-based path planning methods, the Rapidly-exploring Random Trees (RRT) algorithm has been widely studied and applied in the literature. In RRT, how to select a tree to extend or connect is a critical factor, which will greatly influence the efficiency of path planning. In this paper, a novel learning-based multi-RRTs (LM-RRT) approach is proposed for robot path planning in narrow passages. The LM-RRT approach models the tree selection process as a multi-armed bandit problem and uses a reinforcement learning algorithm that learns action values and selects actions with an improved ε-greedy strategy (ε _t -greedy). Compared with previous RRT algorithms, LM-RRT can not only enhance the local space exploration ability of each tree, but also guarantee the efficiency of global path planning. The probabilistic completeness and combinatory optimality of LM-RRT are proved based on the geometric characteristics of the configuration space. Simulation and experimental results show the effectiveness of the proposed LM-RRT approach in single-query path planning problems with narrow passages.     

Boosting imbalanced data learning with Wiener process oversampling

Learning from imbalanced data is a challenging task in a wide range of applications, which attracts significant research efforts from machine learning and data mining community. As a natural approach to this issue, oversampling balances the training samples through replicating existing samples or synthesizing new samples. In general, synthesization outperforms replication by supplying additional information on the minority class. However, the additional information needs to follow the same normal distribution of the training set, which further constrains the new samples within the predefined range of training set. In this paper, we present the Wiener process oversampling (WPO) technique that brings the physics phenomena into sample synthesization. WPO constructs a robust decision region by expanding the attribute ranges in training set while keeping the same normal distribution. The satisfactory performance of WPO can be achieved with much lower computing complexity. In addition, by integrating WPO with ensemble learning, the WPOBoost algorithm outperformsmany prevalent imbalance learning solutions.     

Assessment of crowdsourcing and gamification loss in user-assisted object segmentation

There has been a growing interest in applying human computation – particularly crowdsourcing techniques – to assist in the solution of multimedia, image processing, and computer vision problems which are still too difficult to solve using fully automatic algorithms, and yet relatively easy for humans. In this paper we focus on a specific problem – object segmentation within color images – and compare different solutions which combine color image segmentation algorithms with human efforts, either in the form of an explicit interactive segmentation task or through an implicit collection of valuable human traces with a game. We use Click’n’Cut, a friendly, web-based, interactive segmentation tool that allows segmentation tasks to be assigned to many users, and Ask’nSeek, a game with a purpose designed for object detection and segmentation. The two main contributions of this paper are: (i) We use the results of Click’n’Cut campaigns with different groups of users to examine and quantify the crowdsourcing loss incurred when an interactive segmentation task is assigned to paid crowd-workers, comparing their results to the ones obtained when computer vision experts are asked to perform the same tasks. (ii) Since interactive segmentation tasks are inherently tedious and prone to fatigue, we compare the quality of the results obtained with Click’n’Cut with the ones obtained using a (fun, interactive, and potentially less tedious) game designed for the same purpose. We call this contribution the assessment of the gamification loss, since it refers to how much quality of segmentation results may be lost when we switch to a game-based approach to the same task. We demonstrate that the crowdsourcing loss is significant when using all the data points from workers, but decreases substantially (and becomes comparable to the quality of expert users performing similar tasks) after performing a modest amount of data analysis and filtering out of users whose data are clearly not useful. We also show that – on the other hand – the gamification loss is significantly more severe: the quality of the results drops roughly by half when switching from a focused (yet tedious) task to a more fun and relaxed game environment.     

Interactive Restless Multi-armed Bandit Game and Swarm Intelligence Effect

We obtain the conditions for the emergence of the swarm intelligence effect in an interactive game of restless multi-armed bandit (rMAB). A player competes with multiple agents. Each bandit has a payoff that changes with a probability p _c per round. The agents and player choose one of three options: (1) Exploit (a good bandit), (2) Innovate (asocial learning for a good bandit among n _I randomly chosen bandits), and (3) Observe (social learning for a good bandit). Each agent has two parameters (c, p _obs ) to specify the decision: (i) c, the threshold value for Exploit, and (ii) p _obs , the probability for Observe in learning. The parameters (c, p _obs ) are uniformly distributed. We determine the optimal strategies for the player using complete knowledge about the rMAB. We show whether or not social or asocial learning is more optimal in the (p _c , n _I ) space and define the swarm intelligence effect. We conduct a laboratory experiment (67 subjects) and observe the swarm intelligence effect only if (p _c , n _I ) are chosen so that social learning is far more optimal than asocial learning.     

Towards an EEG-based brain-computer interface for online robot control

According to New York Times, 5.6 million people in the United States are paralyzed to some degree. Motivated by requirements of these paralyzed patients in controlling assisted-devices that support their mobility, we present a novel EEG-based BCI system, which is composed of an Emotive EPOC neuroheadset, a laptop and a Lego Mindstorms NXT robot in this paper. We provide online learning algorithms that consist of k-means clustering and principal component analysis to classify the signals from the headset into corresponding action commands. Moreover, we also discuss how to integrate the Emotiv EPOC headset into the system, and how to integrate the LEGO robot. Finally, we evaluate the proposed online learning algorithms of our BCI system in terms of precision, recall, and the F-measure, and our results show that the algorithms can accurately classify the subjects’ thoughts into corresponding action commands.     

A context-aware approach for trustworthy worker selection in social crowd

Crowdsourcing applications like Amazon Mechanical Turk (AMT) make it possible to address many difficult tasks (e.g., image tagging and sentiment analysis) on the internet and make full use of the wisdom of crowd, where worker quality is one of the most crucial issues for the task owners. Thus, a challenging problem is how to effectively and efficiently select the high quality workers, so that the tasks online can be accomplished successfully under a certain budget. The existing methods on the crowd worker selection problem mainly based on the quality measurement of the crowd workers, those who have to register on the crowdsourcing platforms. With the connect of the OSNs and the crowdsourcing applications, the social contexts like social relationships and social trust between participants and social positions of participants can assist requestors to select one or a group of trustworthy crowdsourcing workers. In this paper, we first present a contextual social network structure and a concept of Strong Social Component (SSC), which emblems a group of workers who have high social contexts values. Then, we propose a novel index for SSC, and a new efficient and effective algorithm C-AWSA to find trustworthy workers, who can complete the tasks with high quality. The results of our experiments conducted on four real OSN datasets illustrate that the superiority of our method in trustworthy worker selection.     

Structural Extension to Logistic Regression: Discriminative Parameter Learning of Belief Net Classifiers

Bayesian belief nets (BN_s) are often used for classification tasks—typically to return the most likely class label for each specified instance. Many BN-learners, however, attempt to find the BN that maximizes a different objective function—viz., likelihood, rather than classification accuracy—typically by first learning an appropriate graphical structure, then finding the parameters for that structure that maximize the likelihood of the data. As these parameters may not maximize the classification accuracy, “discriminative parameter learners” follow the alternative approach of seeking the parameters that maximize conditional likelihood (CL), over the distribution of instances the BN will have to classify. This paper first formally specifies this task, shows how it extends standard logistic regression, and analyzes its inherent sample and computational complexity. We then present a general algorithm for this task, ELR, that applies to arbitrary BN structures and that works effectively even when given incomplete training data. Unfortunately, ELR is not guaranteed to find the parameters that optimize conditional likelihood; moreover, even the optimal-CL parameters need not have minimal classification error. This paper therefore presents empirical evidence that ELR produces effective classifiers, often superior to the ones produced by the standard “generative” algorithms, especially in common situations where the given BN-structure is incorrect.     

FIU-Miner (a fast,integrated, and user-friendly system for data mining) and its applications

The advent of Big Data era drives data analysts from different domains to use data mining techniques for data analysis. However, performing data analysis in a specific domain is not trivial; it often requires complex task configuration, onerous integration of algorithms, and efficient execution in distributed environments. Few efforts have been paid on developing effective tools to facilitate data analysts in conducting complex data analysis tasks. In this paper, we design and implement FIU-Miner, a Fast, Integrated, and User-friendly system to ease data analysis. FIU-Miner allows users to rapidly configure a complex data analysis task without writing a single line of code. It also helps users conveniently import and integrate different analysis programs. Further, it significantly balances resource utilization and task execution in heterogeneous environments. Case studies of real-world applications demonstrate the efficacy and effectiveness of our proposed system.     

Integrating tourist packages and tourist attractions for personalized trip planning based on travel constraints

In recent years, with the upgrading of mobile positioning and the popularity of smart devices, location related research gets a lot of attentions. One of popular issues is the trip planning problem. Although many related scientific or technical literature have been proposed, most of them focused only on tourist attraction recommendation or arrangement meeting some user demands. In fact, to grasp the huge tourism opportunities, more and more tour operators design tourist packages and provide to users. Generally, tourist packages have many advantages such as cheaper ticket price and higher transportation convenience. However, researches on trip planning combining tourist packages have not been mentioned in the past studies. In this research, we present a new approach named Package-Attraction-based Trip Planner (PAT-Planner) to simultaneously combine tourist packages and tourist attractions for personalized trip planning satisfying users’ travel constraints. In PAT-Planner, we first based on user preferences and temporal characteristics to design a Score Inference Model for respectively measuring the score of a tourist package or tourist attraction. Then, we develop the Hybrid Trip-Mine algorithm meeting user travel constraints for personalized trip planning. Besides, we further propose two improvement strategies, namely Score Estimation and Score Bound Tightening, based on Hybrid Trip-Mine to speed up the trip planning efficiency. As far as we know, our study is the first attempt to simultaneously combine tourist packages and tourist attractions on trip planning problem. Through a series of experimental evaluations and case studies using the collected Gowalla datasets, PAT-Planner demonstrates excellent planning effects.     

Tackling heterogeneous concept drift with the Self-Adjusting Memory (SAM)

Instance matching is the problem of determining whether two instances describe the same real-world entity or not. Instance matching plays a key role in data integration and data cleansing, especially for building a knowledge base. For example, we can regard each article in encyclopedias as an instance, and a group of articles which refers to the same real-world object as an entity. Therefore, articles about Washington should be distinguished and grouped into different entities such as Washington, D.C (the capital of the USA), George Washington (first president of the USA), Washington (a state of the USA), Washington (a village in West Sussex, England), Washington F.C. (a football club based in Washington, Tyne and Wear, England), Washington, D.C. (a novel). In this paper, we proposed a novel instance matching approach Active Instance Matching with Pairwise Constraints, which can bring the human into the loop of instance matching. The proposed approach can generate candidate pairs in advance to reduce the computational complexity, and then iteratively select the most informative pairs according to the uncertainty, influence, connectivity and diversity of pairs. We evaluated our approach one two publicly available datasets AMINER and WIDE-NUS and then applied our approach to the two large-scale real-world datasets, Baidu Baike and Hudong Baike, to build a Chinese knowledge base. The experiments and practice illustrate the effectiveness of our approach.     

An Improved Extended Active Observer for Adaptive Control of A <Emphasis Type="Italic">n</Emphasis><Emphasis Type="Italic">−</Emphasis>DOF Robot Manipulator

A novel algorithm for simultaneous force estimation and friction compensation of constrained motion of robot manipulators is presented. This represents an extension of the improved extended active observer (IEAOB) algorithm reported earlier and proposes a higher order IEAOB or N?th order IEAOB (IEAOB ?N) for a n?DOF robot manipulator. Central to this observer is the use of extra system states modeled as a Gauss-Markov (GM) formulation to estimate the force and disturbances including robot inertial parameters and friction. The stability of IEAOB ?N is verified through stability analysis. The IEAOB-1 is validated by applying it to a Phantom Omni haptic device against a Nicosia observer, disturbance observer (DOB)/reaction torque observer (RTOB), and nonlinear disturbance observer (NDO), respectively. The results show that the proposed IEAOB-1 is superior to the compared observers in terms of force estimation. Then, the performance of the IEAOB ? N is experimentally studied and compared to the IEAOB-1. Results demonstrate that the IEAOB ? N has an improved capability in tracking nonlinear external forces.     

Selective A<Emphasis Type="Italic">n</Emphasis>DE for large data learning: a low-bias memory constrained approach

Learning from data that are too big to fit into memory poses great challenges to currently available learning approaches. Averaged n-Dependence Estimators (AnDE) allows for a flexible learning from out-of-core data, by varying the value of n (number of super parents). Hence, AnDE is especially appropriate for learning from large quantities of data. Memory requirement in AnDE, however, increases combinatorially with the number of attributes and the parameter n. In large data learning, number of attributes is often large and we also expect high n to achieve low-bias classification. In order to achieve the lower bias of AnDE with higher n but with less memory requirement, we propose a memory constrained selective AnDE algorithm, in which two passes of learning through training examples are involved. The first pass performs attribute selection on super parents according to available memory, whereas the second one learns an AnDE model with parents only on the selected attributes. Extensive experiments show that the new selective AnDE has considerably lower bias and prediction error relative to A\(n'\)DE, where \(n' = n-1\), while maintaining the same space complexity and similar time complexity. The proposed algorithm works well on categorical data. Numerical data sets need to be discretized first.     

Affective learning: improving engagement and enhancing learning with affect-aware feedback

This paper describes the design and ecologically valid evaluation of a learner model that lies at the heart of an intelligent learning environment called iTalk2Learn. A core objective of the learner model is to adapt formative feedback based on students’ affective states. Types of adaptation include what type of formative feedback should be provided and how it should be presented. Two Bayesian networks trained with data gathered in a series of Wizard-of-Oz studies are used for the adaptation process. This paper reports results from a quasi-experimental evaluation, in authentic classroom settings, which compared a version of iTalk2Learn that adapted feedback based on students’ affective states as they were talking aloud with the system (the affect condition) with one that provided feedback based only on the students’ performance (the non-affect condition). Our results suggest that affect-aware support contributes to reducing boredom and off-task behavior, and may have an effect on learning. We discuss the internal and ecological validity of the study, in light of pedagogical considerations that informed the design of the two conditions. Overall, the results of the study have implications both for the design of educational technology and for classroom approaches to teaching, because they highlight the important role that affect-aware modelling plays in the adaptive delivery of formative feedback to support learning.     

A closed asynchronous dynamic model of cellular learning automata and its application to peer-to-peer networks

Cellular Learning Automata (CLAs) are hybrid models obtained from combination of Cellular Automata (CAs) and Learning Automata (LAs). These models can be either open or closed. In closed CLAs, the states of neighboring cells of each cell called local environment affect on the action selection process of the LA of that cell whereas in open CLAs, each cell, in addition to its local environment has an exclusive environment which is observed by the cell only and the global environment which can be observed by all the cells in CLA. In dynamic models of CLAs, one of their aspects such as structure, local rule or neighborhood radius may change during the evolution of the CLA. CLAs can also be classified as synchronous CLAs or asynchronous CLAs. In a synchronous CLA, all LAs in different cells are activated synchronously whereas in an asynchronous CLA, the LAs in different cells are activated asynchronously. In this paper, a new closed asynchronous dynamic model of CLA whose structure and the number of LAs in each cell may vary with time has been introduced. To show the potential of the proposed model, a landmark clustering algorithm for solving topology mismatch problem in unstructured peer-to-peer networks has been proposed. To evaluate the proposed algorithm, computer simulations have been conducted and then the results are compared with the results obtained for two existing algorithms for solving topology mismatch problem. It has been shown that the proposed algorithm is superior to the existing algorithms with respect to communication delay and average round-trip time between peers within clusters.