Search

Interest in the Wireless Medical Sensor Network (WMSN) is rapidly gaining attention thanks to recent advances in semiconductors and wireless communication. However, by virtue of the sensitive medical applications and the stringent resource constraints, there is a need to develop a routing protocol to fulfill WMSN requirements in terms of delivery reliability, attack resiliency, computational overhead and energy efficiency. This doctoral research therefore aims to advance the state of the art in routing by proposing a lightweight, reliable routing protocol for WMSN. Ensuring a reliable path between the source and the destination requires making trustaware routing decisions to avoid untrustworthy paths. A lightweight and effective Trust Management System (TMS) has been developed to evaluate the trust relationship between the sensor nodes with a view to differentiating between trustworthy nodes and untrustworthy ones. Moreover, a resource-conservative Reinforcement Learning (RL) model has been proposed to reduce the computational overhead, along with two updating methods to speed up the algorithm convergence. The reward function is re-defined as a punishment, combining the proposed trust management system to defend against well-known dropping attacks. Furthermore, with a view to addressing the inborn overestimation problem in Q-learning-based routing protocols, we adopted double Q-learning to overcome the positive bias of using a single estimator. An energy model is integrated with the reward function to enhance the network lifetime and balance energy consumption across the network. The proposed energy model uses only local information to avoid the resource burdens and the security concerns of exchanging energy information. Finally, a realistic trust management testbed has been developed to overcome the limitations of using numerical analysis to evaluate proposed trust management schemes, particularly in the context of WMSN. The proposed testbed has been developed as an additional module to the NS-3 simulator to fulfill usability, generalisability, flexibility, scalability and high-performance requirements.

Multi-Agent Reinforcement Learning (MARL) faces numerous challenges in partially-observable environments due to limited information and the non-stationarity of the learning process. This study aims to determine the optimal rate and type of information sharing in MARL algorithms to improve performance in such environments. Here, we benchmark the Independent Q-Learning (IQL) and Independent Proximal Policy Optimization (IPPO) algorithms, modifying them to facilitate various forms of information sharing in the Level-Based Foraging environment. Our experimental results reaffirm theorized downsides of na¨ıve information sharing from scientific literature and demonstrate that optimal sharing rates may be an additional hyperparameter for optimization: notably, when allowing agents to choose when to share information, models perform competitively while converging to rates of sharing as low as 10% while achieving improved short-term returns. Additionally, we find that pairing information about agents’ actions with their observations yields the highest returns, possibly allowing agent networks to parameterize each others’ policies.

This project is based on a request from the Kroger grocery store to automate its fresh meat department. The project is divided into three parts: first, Catia modeling the fresh meat department and designing two robots based on UR10 robotic arms and four-wheeled electric vehicles. In the second part, the reinforcement learning algorithm, Q-learning, is applied in the path planning of the robot path calculation. In the third part, the human-robot interaction system uses an interface developed by OpenCV and Mediapipe's hand recognition package. Simulation and practical operation are performed in this project for these three parts. The simulation results and calculation results verify the feasibility of the design. The robot can pick, pack, label, and replenish tasks. The human-robot interaction interface can clearly distinguish the customer's needs. The robustness of the Q-learning algorithm for path planning meets the expected standard and can complete the path planning in a short time. The paper concludes with a market price analysis and a comparative analysis of the profitability of this project.

This thesis studies Object-Oriented Markov Decision Processes (OO-MDPs), which extend MDPs with prior knowledge about the shared dynamics of similar objects in the environment. Existing work presents model-based algorithms that leverage the properties of OO-MDPs and adhere to the Knows What It Knows (KWIK) framework. In practice, models may not be easy to estimate and the KWIK framework may still lead to slow performance in a reinforcement learning context. In this thesis, I first introduce a new model-free learning algorithm for OO-MDPs based on Q-Learning. Though my approach is not KWIK, I show empirically that it exhibits significantly faster convergence than the KWIK and flat baselines. Next, I extend hierarchical reinforcement learning (HRL) to use OO-MDPs in the same manner. HRL uses a task hierarchy as prior information to reduce the overall problem into a set of smaller tasks. I show that HRL and OO-MDPs have a natural synergy, and I propose a novel model-free OO-HRL algorithm. I show empirically that this algorithm has better sample complexity than either HRL or OO-MDP algorithms alone.

Influenza is a seasonal viral disease affecting over 1 billion people annually around the globe, as reported by the World Health Organization (WHO). The influenza virus has been around for decades causing multiple pandemics and encouraging researchers to perform extensive analysis of its evolutionary patterns. Current research uses phylogenetic trees as the basis to guide population genetics and other phenotypic characteristics when describing the evolution of the influenza genome. Phylogenetic trees are one form of representing the evolutionary trends of sequenced genomes, but that do not capture the multidimensional complexity of mutational pathways. We suggest representing antigenic drifts within influenza A/H1N1 hemagglutinin (HA) protein as a graph, $G = (V, E)$, where $V$ is the set of vertices representing each possible sequence and $E$ is the set of edges representing single amino acid substitutions. Each transition is characterized by a Malthusian fitness model incorporating the genetic adaptation, vaccine similarity, and historical epidemiological response using mortality as the metric where available. Applying reinforcement learning with the vertices as states, edges as actions, and fitness as the reward, we learn the high likelihood mutational pathways and optimal policy, without exploring the entire space of the graph, $G$. Our average predicted versus actual sequence distance of $3.6 \pm 1.2$ amino acids indicates that our novel approach of using naive Q-learning can assist with influenza strain predictions, thus improving vaccine selection for future disease seasons.

With an emerging interest in personalized medicine and quality healthcare, the design of clinical trials that incorporates multiple stages of randomization and intervention, for example, a sequential multiple assignment randomized trial (SMART), has become a popular choice for investigators as it facilitates the construction and analysis of dynamic treatment regimes (DTRs). There exists a comprehensive body of literature on various statistical methods to analyze data collected from such trials and estimate the optimal DTR for an individual subject, among which Q-learning with linear regression is widely used due to its simplicity and ease of interpretation. This thesis discusses three important challenges that cause problems in the implementation of Q-learning and proposes multiple modifications of Q-learning to address them.The first challenge arises from the repeatedly monitored outcome of interest at intermediate stages of randomization and at longer follow-up intervals after the final stage of randomization. Clinical investigators are usually interested in identifying the optimal DTR and estimating the outcome trajectory under the optimal DTR. However, in the presence of stagewise repeated-measures outcomes, standard Q-learning fails to provide point estimates of the optimal trajectory with time-specific heterogeneous causal effects. To address this problem, we propose a modified algorithm of Q-learning with a generalized estimating equation to estimate each Q-function. The second challenge is model misspecification. Model misspecification is a common problem in Q-learning, but little attention has been given to its impact when treatment effects are heterogeneous across subjects. We describe the integrative impact of two possible types of model misspecification related to treatment effect heterogeneity: unexplained early-stage treatment effects in late-stage main effect model, and misspecified linearity between pseudo-outcomes and predictors as a result of the optimization operation. The proposed method, aiming to deal with both types of misspecification concomitantly, builds interactive models into residual-modified parametric Q-learning. The third challenge is generalizing modified Q-learning to dichotomous outcomes. It is difficult to include informative residuals from estimation of late-stage models into early-stage pseudo-outcomes due to the non-identity link function. We propose a modification based on monotonicity of preferences to address model misspecification in Q-learning with probit regression. The improvement in robustness of the proposed modification is subject to the extent of model misspecification and can be limited. Thus, we take a latent variable approach and propose a novel algorithm using sampled surrogates of the underlying continuous outcome conditional on the binary observations. The methods proposed in this thesis are assessed via simulations and illustrated using the M-bridge study, a SMART with embedded tailoring which develops and evaluates adaptive interventions for preventing binge drinking among college students.

Hanabi is a cooperative card game with hidden information that requires cooperation and communication between the players. For a machine learning agent to be successful at the Hanabi, it will have to learn how to communicate and infer information from the communication of other players. To approach the problem of Hanabi the machine learning methods of Q-learning and Evolutionary algorithm are proposed as potential solutions. The agents that were created using the method are shown to not achieve human levels of communication.

Reinforcement learning has become a popular research topic due to the recent successes in combining deep learning value function estimation and reinforcement learning. Because of the popularity of these methods, deep learning has become the de facto standard for function approximation in reinforcement learning. However, other function approximation methods offer advantages in speed, ease of use, interpretability and stability. In our first essay, we examine several existing reinforcement learning methods that use decision trees for function approximation. Results of testing on a benchmark reinforcement learning problem show promising results for decision tree based methods. In addition, we propose the use of online random forests for reinforcement learning which show competitive results.In the second essay, we discuss accelerated boosting of partially linear models. Partially linear additive models are a powerful and flexible technique for modeling complex data. However, automatic variable selection to linear, nonlinear and uninformative terms can be computationally expensive. We propose using accelerated twin boosting to automatically select these terms and fit a partially linear additive model. Acceleration reduces the computational effort versus non-accelerated methods while maintaining accuracy and ease of use. Twin boosting is adopted to improve variable selection of accelerated boosting. We demonstrate the results of our proposed method on simulated and real data sets. We show that accelerated twin boosting results in accurate, parsimonious models with substantially less computation than non-accelerated twin boosting.

Traffic congestion and safety has become a major issue in the modern world's commute. Congestion has been causing people to travel billions of hours more and to purchase billions of gallons of fuel extra which account to congestion cost of billions of dollars. Autonomous driving vehicles have been one solution to this problem because of their huge impact on efficiency, pollution, and human safety. Also, extensive research has been carried out on control design of vehicular platoons because a further improvement in traffic throughput while not compromising the safety is possible when the vehicles in the platoon are provided with better predictive abilities. Motion control is a key area of autonomous driving research that handles moving parts of vehicles in a deliberate and controlled manner. A widely worked on problem in motion control concerned with time parameterized reference tracking is trajectory tracking. Having an efficient and effective tracking algorithm embedded in the autonomous driving system is the key for better performance in terms of resources consumed and tracking error. Many tracking control algorithms in literature rely on an accurate model of the vehicle and often, it can be an intimidating task to come up with an accurate model taking into consideration various conditions like friction, heat effects, ageing processes etc. And typically, control algorithms rely on periodic execution of the tasks that update the control actions, but such updates might not be required, which result in unnecessary actions that waste resources. The main focus of this work is to design an intermittent model-free optimal control algorithm in order to enable autonomous vehicles to track trajectories at high-speeds. To obtain a solution which is model-free, a Q-learning setup with an actor-network to approximate the optimal intermittent controller and a critic network to approximate the optimal cost, resulting in the appropriate tuning laws is considered.

Reinforcement learning models learn the optimal policy by interacting with the environment and observing the states and rewards. If the rewards that the model observes are noisy then learning an optimal policy becomes a difficult task. We present an approach that can enhance the performance of reinforcement learning models in the presence of noisy rewards. Along with the standard reinforcement learning model, we propose to use a noise filter which estimates the true reward that the model should receive. The noise filter is designed using a non-linear approximator. Through various experiments we demonstrate that this approach improves the performance of the model in the presence of noisy rewards

Autonomous systems which are designed to assist humans in complex environments, are often required to reliably operate under uncertainty. When probabilistic models for uncertainty are not available, the game-theoretic framework for adversarial/cooperative interactions allows us to solve problems for autonomous systems, such as control of uncertain dynamical systems, modeling biological systems, and deployment of sensor networks. This work focuses on decision-making and control problems for autonomous agents in uncertain environments. Characteristic sources of such uncertainty are wind or oceanic flows, radiation fields, and moving obstacles. In our approach, we model the agent-environment interactions induced by these sources of uncertainty as the actions of an adversary, which tries to prevent the agent from achieving its objective (e.g., reaching a target location). This modeling naturally leads to the formulation of a dynamic game between the autonomous agent and its environment. Control problems of autonomous agents that are subject to uncertain dynamic influences such as strong winds, fit into the structure of two-player zero-sum differential games. Many modern decision-making problems, however, cannot be put under the umbrella of zero-sum games because they involve complex interplay between multiple agents, which is not purely antagonistic. In this context, we address a special class of decision-making and path-planning problems, for autonomous agents that aim to reach a specified target set while avoiding multiple adversarial elements (such as mobile agents or obstacles). This class of problems, referred to as reach-avoid problems, corresponds to multi-player non-zero-sum dynamic games. Multi-player dynamic games typically require solving coupled partial differential equations, which is computationally and temporally expensive, if at all tractable. This intractability is particularly true, for problems of high dimensionality, and if there are agents in the game which have multiple objectives. For this reason, approximate solutions to dynamic multi-agent games are desirable in practice. Considering the binary objective of our agent of interest, we propose three approaches to the path-planning problem. Each approach is based on the characterization of risk to the agent, and uses a distinct method to determine a feasible solution to the multi-agent game. First, we propose an approximate divide-and-conquer approach that allows us to compute the global path for the agent of interest by concatenating local paths computed on a dynamic graph-abstraction of the environment. Through extensive simulations, we have demonstrated the effectiveness of the proposed approach. However, the proposed method does not guarantee global optimality or completeness of the solution, and also incurs considerable computational cost at each step. To improve computational tractability of the path-planning problem, next, we propose a feedback strategy based on greedy minimization of risk, where the risk metric is characterized with regard to the dual objective of the agent of interest. The same risk metric also aids us in partitioning the state-space of the game, which is useful to infer the outcome of the game from its initial conditions. The feedback strategy is computationally simple. Further, through numerical simulations, this approach has been found to be effective in a large number of cases, in guiding the autonomous vehicle to its target set. In order to further improve the target-reaching capability of the autonomous agent, we propose a third approach, a reduction of the dynamic multi-player game to a sequence of single-act games, one played at each time step. The proposed approach is also easy to implement and also does not incur significant loss of optimality. At each step, the optimal set of player strategies can be calculated efficiently and reliably via convex programming tools. More importantly, the proposed sequential formulation of the dynamic game allows us to account for the effect of the current actions of the agents on the final outcome of the original dynamic game. However, the payoffs of future games are altered by the past games and consequently, the equilibria for the single-act games (stage-wise equilibria) might not be optimal when the dynamic game is viewed as a whole. The choice of stage-wise equilibria can be improved by recording past actions and their effect on future payoffs. Drawing upon the history of actions and outcome patterns if any, we can learn to make better choices in the present. For multi-agent games with multiple non-aligned objectives for each agent, learning processes can aid in high-level switching between the optimal strategies corresponding to individual objectives. We propose the use of model-free reinforcement learning methods to obtain a feedback policy for the agent of interest. The challenges here, are to characterize an appropriate reward function, particularly under consideration of multiple objectives for the agent, and also to optimize parameters of the learning process. The goal of this thesis is to contribute a solid framework, which is based on game theory, and combines analytical and computational techniques, to address the problem of path-planning for an autonomous agent with multiple objectives in uncertain environments

Part of the implementation of Reinforcement Learning is constructing a regression of values against states and actions and using that regression model to optimize over actions for a given state. One such common regression technique is that of a decision tree; or in the case of continuous input, a regression tree. In such a case, we fix the states and optimize over actions; however, standard regression trees do not easily optimize over a subset of the input variables\cite{Card1993}. The technique we propose in this thesis is a hybrid of regression trees and kernel regression. First, a regression tree splits over state variables at a macro level, then kernel regression models the effects of actions with a smooth function at a micro level. Then non-linear optimization is used to optimize the kernel regressed function to find the best action and get a precise prediction of its value for any given state. This ``best action" is then stored in the tree and is instantly retrieved upon making decisions. This is not only more appropriate for problems with continuous output, but also for problems with a discrete output since it also generalizes the knowledge over actions as well as states, providing for smarter decision-making. The capabilities of this technique are observed for a time series constructed to realistically model a stock problem.

While state-of-the-art machine learning models are deep, large-scale, sequential and highly nonconvex, the backbone of modern learning algorithms are simple algorithms such as stochastic gradient descent, gradient descent with momentum or Q-learning (in the case of reinforcement learning tasks). A basic question endures---why do simple algorithms work so well even in these challenging settings?To answer above question, this thesis focuses on four concrete and fundamental questions:- In nonconvex optimization, can (stochastic) gradient descent or its variants escape saddle points efficiently?- Is gradient descent with momentum provably faster than gradient descent in the general nonconvex setting?- In nonconvex-nonconcave minmax optimization, what is a proper definition of local optima and is gradient descent ascent game-theoretically meaningful?- In reinforcement learning, is Q-learning sample efficient?This thesis provides the first line of provably positive answers to all above questions. In particular, this thesis will show that although the standard versions of these classical algorithms do not enjoy good theoretical properties in the worst case, simple modifications are sufficient to grant them desirable behaviors, which explain the underlying mechanisms behind their favorable performance in practice.

Energy optimization for plug-in hybrid electric vehicles (PHEVs) is a challenging problem due to its system complexity and various constraints. In this research, we present a Q-learning based in-vehicle model-free solution that can robustly converge to the optimal control. The proposed algorithms combine neuro-dynamic programming (NDP) with future trip information to effectively estimate the expected future energy cost (expected cost-to-go) for a given vehicle state and control actions. The convergence of those learning algorithms is demonstrated on both fixed and randomly selected drive cycles. Based on the characteristics of these learning algorithms, we propose a two-stage deployment solution for PHEV power management applications. We will also introduce a new initialization strategy that combines optimal learning with a properly selected penalty function. Such initialization can reduce the learning convergence time by 70%, which has huge impact on in-vehicle implementation. Finally, we develop a neural network (NN) for the battery state-of-charge (SoC) prediction, rendering our power management controller completely model-free.

Reinforcement learning (RL) can cope with uncertainty in partially observable environments. However, RL algorithms face a challenge when the context of the learning problem changes. A change in context alters the goal of the bot, the value function associated with the state-action map learnt by the bot before the change occurred, and sometimes even the definition of states and the set of available actions. Simple RL-based bots will fail to act in a goal-oriented manner when such a change in context occurs. This thesis proposes a hierarchical cognitive agent architecture that allows a bot to learn how to act in similar environments and adapt its action to suit multiple contexts. It fuses two cognitive architectures from the literature. The first is the Executive-Process Interaction Control (EPIC) architecture that represents both perceptual and motor functions, and cognitive processes required for decision making. The second is the Society of Minds (SoM) architecture that uses an ensemble of decision-making agents and the K-line concept to fuse the ensemble using the non-compromise principle. The introduction of this architecture opens two research directions: (1) the mechanism of information perception, information processing and archiving (EPIC part), and (2) the learning process in such architecture to make decisions (SoM part). The main aim of this thesis is to develop a RL framework for the SoM part of the architecture while assuming that the EPIC part provides perfect information. The novel RL based architecture, called Selective K-line for Mixture of Q-Learners (SKMQ), is tested for addressing the issue of RL algorithms mentioned earlier on changing environment and context problems. In SKMQ, the hierarchy has three levels. On the lowest level exists several basic skill agents (BSAs) that learn to specialise on specific contexts. BSAs are then used by Planner Agents (PA) on the second level of the hierarchy to form plans: sequences of BSAs to use in different environments. Within the root at the top of the tree resides an adaptive agent (AA) that acts as the Kline responsible to choose an appropriate planner agent for different contexts. Q-learning is used to train the individual BSAs on a specific, but changing, context, and at the meta-level, the K-line learns to use PAs when transiting between contexts. A new early stopping criterion for Q-learning to mitigate loss of valuable information during training is used by BSAs. The K-line is trained with a Q-learning algorithm with a synthesized reward function representing a balance between two objectives: maximise effectiveness or mission success, and maximise efficiency by minimising the cost and time when transiting across contexts. The proposed architecture and algorithms are shown to afford the bot abilities to learn basic skills and switch between different operating contexts.

Nowadays, pharmacological practices are focused on a single best treatment to treat a disease which sounds impractical as the same treatment may not work the same way for every patient. Thus, there is a need of shift towards more patient-centric rather than disease-centric approach, in which personal characteristics of a patient or biomarkers are used to determine the tailored optimal treatment. The “one size fits all” concept is contradicted by research area of personalized medicine. The Sequential Multiple Assignment Randomized Trial (SMART) is a multi-stage trials to inform the development of dynamic treatment regimens (DTR’s). In SMART, a subject is randomized through various stages of treatment where each stage corresponds to a treatment decision. These types of adaptive interventions are individualized and are repeatedly adjusted across time based on patient’s individual clinical characteristics and ongoing performance. The reinforcement learning (Q-learning), a computational algorithm for optimization of treatment regimens to maximize desired clinical outcome is used in optimizing the sequence of treatments. This statistical model contains regression analysis for function approximation of data from clinical trials. The model will predict a series of regimens across time, depending on the biomarkers of a new participant for optimizing the weight management decision rules. Additionally, for implementing reinforcement learning algorithm, as it is one of the machine learning approach there should be a training data from which we can train the model or in other words approximate the function, Q-functions. Then the approximated functions of the model should be evaluated and after the evaluation they should be further tested for applying the treatment rule to future patients. Thus, in this thesis first the dataset obtained from Sanford Health is first restructured, to make it conducive for our model utilization. The restructured training data is used in regression analysis for approximating the Q-functions. The regression analysis gives the estimates of coefficients associated to each covariate in the regression function. The evaluation of model goodness-of-fit and fulfillment of underlying assumptions of simple linear regression are performed using regression summary table and residual diagnostic plots. As a two stage SMART design is put into practice, the Q-functions for these two stages are needed to be estimated through multiple regression using linear model. Now, finally after analyzing the fit adequacy the model is applied for prescribing treatment rules to future patients. The prognostic and predictive covariates of new patient is acquired and the optimal treatment rule for each treatment decision stage is assigned as the treatment that results in maximum estimated values of Q-functions. The estimated values of each regime were also computed using the value estimator function and regime that has the maximum estimated value was chosen as optimal treatment decision rule.

As the field of robotic and humanoid systems expand, more research is being done on how to best control systems to perform complex, smart tasks. Many supervised learning and classification techniques require large datasets, and only result in the system mimicking what it was given. The sequential relationship within datasets used for task learning results in Markov decision problems that traditional classification algorithms cannot solve. Reinforcement learning helps to solve these types of problems using a reward/punishment and exploration/exploitation methodology without the need for datasets. While this works for simple systems, complex systems are more difficult to teach using traditional reinforcement learning. Often these systems have complex, non-linear, non-intuitive cost functions which make it near impossible to model. Inverse reinforcement learning, or apprenticeship learning algorithms, learn complex cost functions based on input from an expert system. Deep learning has also made a large impact in learning complex systems, and has achieved state of the art results in several applications. Using methods from apprenticeship learning and deep learning a system can be taught complex tasks from watching an expert. It is shown here how well these types of networks solve a specific task, and how well they generalize and understand the task through raw pixel data from an expert.

Mobile applications are growing in popularity and pose new problems in the area of software testing. In particular, mobile applications heavily depend upon user interactions and a dynamically changing environment of system events. In this thesis, we focus on user-driven events and use Q-learning, a reinforcement machine learning algorithm, to generate tests for Android applications under test (AUT). We implement a framework that automates the generation of GUI test cases by using our Q-learning approach and compare it to a uniform random (UR) implementation. A novel feature of our approach is that we generate user-driven event sequences through the GUI, without the source code or the model of the AUT. Hence, considerable amount of cost and time are saved by avoiding the need for model generation for generating the tests. Our results show that the systematic path exploration used by Q-learning results in higher average code coverage in comparison to the uniform random approach.

In the field of survey methodology, optimizing contact strategies helps organizations increase response rates using their allocated budget. Markov Decision Processes (MDP) are widely used to model decision-making strategies in situations where the outcomes have a random component. In this research, we use MDPs and adaptive sampling techniques to construct a strategy that, based on target audience characteristics, suggests the best contact policy. The data we use comes from the First Destination Survey conducted by the Office of Career Services at Georgia Southern University. The constructed model is quite flexible and can be used by other organizations to optimize their contact strategies.

Search is an essential technology for various robotic applications and it is also central to human daily activities. Searching for targets efficiently consists of NP-hard problems, but young children can search for targets very efficiently . How humans search for targets efficiently is still a mystery. Hence, two central questions are as follows: First, how do humans search for targets efficiently ? Second, how can robots learn to search like humans? The central goal of this dissertation is to explore these two questions, analyzing and modeling human search behavior and then applying the findings to robot search. This thesis is organized in three parts--human search analysis, problem reformulation, and learning in robot search. In the first part, the goal is to analyze and model human search behavior. In the experiments, human subjects remotely control a mobile robot to search for a target through teleoperation. Their search data are collected for further analysis. A novel framework consisting structure learning and K-means clustering is proposed to model and analyze humans search behavior. The analysis of the experimental data demonstrates that (1) humans are able to solve the complex search task by breaking it up into smaller tasks (so called subgoal hypothesis); and (2) humans consider both coverage and motion cost while searching. In the second part, the goal is to derive an objective function considering coverage and motion cost. The objective of search is to maximize the probability of target detection while covering most of the environment in minimum time. The robot needs to consider three objectives: (1) maximal coverage; (2) maximal probability of detection; and (3) minimum-time trajectory planning. However, all these objectives are NP-hard. Since two of these objective functions are submodular, the search problem can be reformulated as maximizing the cumulative probability of detection (PD) with motion cost. The proof shows that greedy algorithms give near-optimal subgoals with high probability. In the last part, the approach is to learn to search through sequential perception and actions. Since the PD function and cost-to-go (CTG) function depend on the environment, the robot needs to learn both the PD function and CTG function. To make the learning process of the PD function tractable, a technique based on Spatial Fourier Sparse Set (SFSS) is proposed that takes advantage of the structure in the relationship between the robot's spatial conguration and its environmental sensing. Q-learning is proposed to learn the CTG function. The learned PD and CTG functions can then be used to generate subgoals for search tasks. Based on compressed sensing theory, the proposed SFSS is able to learn a submodular function with m samples, where m

Teaching an autonomous agent to perform tasks that are simple to humans can be complex, especially when the task requires successive steps, has a low likelihood of successful completion with a brute force approach, and when the solution space is too large or too complex to be explicitly encoded. Reinforcement learning algorithms are particularly suited to such situations, and are based on rewards that help the agent to find the optimal action to execute given a certain state. The task investigated in this thesis is a modified form of the Block Design (BD) and Block Design Multiple Choice (BDMC) subtests, used by the Fourth Edition of the Wechsler Intelligence Scale for Children (WISC-IV) to partially assess childrens' learning abilities. This thesis investigates the implementation, training, and performance of two reinforcement learning architectures for this problem: Soar-RL, a production system capable of reinforcement learning, and a Q-learning neural network. The objective is to help define the advantages and disadvantages of solving problems using these architectures. This thesis will show that Soar is intuitive for implementation and is able to find an optimal policy, although it is limited by its execution of exploratory actions. The neural network is also able to find an optimal policy and outperforms Soar, but the convergence of the solution is highly dependent on the architecture of the neural network.

Military, Medical, Exploratory, and Commercial robots have much to gain from exchanging wheels for legs. However, the equations of motion of dynamic bipedal walker models are highly coupled and non-linear, making the selection of an appropriate control scheme difficult. A temporal difference reinforcement learning method known as Q-learning develops complex control policies through environmental exploration and exploitation. As a proof of concept, Q-learning was applied through simulation to a benchmark single pendulum swing-up/balance task; the value function was first approximated with a look-up table, and then an artificial neural network. We then applied Evolutionary Function Approximation for Reinforcement Learning to effectively control the swing-leg and torso of a 3 degree of freedom active dynamic bipedal walker in simulation. The model began each episode in a stationary vertical configuration. At each time-step the learning agent was rewarded for horizontal hip displacement scaled by torso altitude--which promoted faster walking while maintaining an upright posture--and one of six coupled torque activations were applied through two first-order filters. Over the course of 23 generations, an approximation of the value function was evolved which enabled walking at an average speed of 0.36 m/s. The agent oscillated the torso forward then backward at each step, driving the walker forward for forty-two steps in thirty seconds without falling over. This work represents the foundation for improvements in anthropomorphic bipedal robots, exoskeleton mechanisms to assist in walking, and smart prosthetics.

"Multi-Agent systems" is a topic for a lot of research, especially research involving strategy, evolution and cooperation among various agents. Various learning algorithm schemes have been proposed such as reinforcement learning and evolutionary computing. In this thesis two solutions to a multi-agent herding problem are presented. One solution is based on Q-learning algorithm, while the other is based on modeling of artificial immune system. Q-learning solution for the herding problem is developed, using region-based local learning for each individual agent. Individual and batch processing reinforcement algorithms are implemented for non-cooperative agents. Agents in this formulation do not share any information or knowledge. Issues such as computational requirements, and convergence are discussed. An idiotopic artificial immune network is proposed that includes individual B-cell model for agents and T-cell model for controlling the interaction among these agents. Two network models are proposed--one for evolving group behavior/strategy arbitration and the other for individual action selection. A comparative study of the Q-learning solution and the immune network solution is done on important aspects such as computation requirements, predictability, and convergence.

Dynamic noncooperative multiagent systems are systems where self-interested agents interact with each other and their interactions change over time. We investigate the problem of learning and decision making in such systems. We model the systems in the framework of general-sum stochastic games with incomplete information. We design a multiagent Q-learning method, and prove its convergence in the framework of stochastic games. The standard Q-learning method, a reinforcement learning method, was originally designed for single-agent systems. Its convergence was proved for Markov decision processes, which are single-agent problems. Our extension broadens the framework of reinforcement learning, and helps to establish the theoretical foundation for applying it to multiagent systems. We prove that our learning algorithm converges to a Nash equilibrium under certain restrictions on the game structure during learning. In our simulations of a grid-world game, the restrictions are relaxed and our learning method still converges. In addition to model-free reinforcement learning, we have also studied model-based learning where agents form models of others and update their models through observations of the environment. We find that agents' mutual learning can lead to a conjectural equilibrium, where the agents' models of the others are fulfilled, and each agent behaves optimally given its expectation. Such an equilibrium state may be suboptimal. The agents may be worse off than had they not attempted to learn the models of others at all. This poses a pitfall for multiagent learning. We also analyzed the problem of recursive modeling in a dynamic game framework. This differs from previous work which studied recursive modeling in static or repeated games. We implement various levels of recursive model in a simulated double auction market. Our experiments show that performance of an agent can be quite sensitive to its assumptions about the policies of other agents, and when there is substantial uncertainty about the level of sophistication of other agents, reducing the level of recursion might be the best policy.

A distributed reinforcement-learning system is designed and implemented on a mobile robot for the study of complex task decomposition in real robot learning environments. The Distributed Q-learning Classifier System (DQLCS) is evolved from the standard Learning Classifier System (LCS) proposed by J.H. Holland. Two of the limitations of the standard LCS are its monolithic nature and its complex apportionment of credit scheme, the bucket brigade algorithm (BBA). The DQLCS addresses both of these problems as well as the inherent difficulties faced by learning systems operating in real environments. We introduce Q-learning as the apportionment of credit component of the DQLCS, and we develop a distributed learning architecture to facilitate complex task decomposition. Based upon dynamic programming, the Q-learning update equation is derived and its advantages over the complex BBA are discussed. The distributed architecture is implemented to provide for faster learning by allowing the system to effectively decrease the size of the problem space it must explore. Holistic and monolithic shaping approaches are used to distribute reward among the learning modules of the DQLCS in a variety of real robot learning experiments. The results of these experiments support the DQLCS as a useful reinforcement learning paradigm and suggest future areas of study in distributed learning systems.