Search

Approaches that support the decision-making of self-adaptive and autonomous systems (SAS) often consider an idealized situation where (i) the system's state is treated as fully observable by the monitoring infrastructure, and (ii) adaptation actions are assumed to have known, deterministic effects over the system. However, in practice, the system's state may not be fully observable, and the adaptation actions may produce unexpected effects due to uncertain factors. This article presents a novel probabilistic approach to quantify the uncertainty associated with the effects of adaptation actions on the state of a SAS. Supported by Bayesian inference and POMDPs (Partially-Observable Markov Decision Processes), these effects are translated into the satisfaction levels of the non-functional requirements (NFRs) to, therefore, drive the decision-making. The approach has been applied to two substantial case studies from the networking and Internet of Things (IoT) domains, using two different POMDP solvers. The results show that the approach delivers statistically significant improvements in supporting decision-making for SAS. [ABSTRACT FROM AUTHOR]

Teaching is an intuitive social activity that requires reason-ing about and influencing the mind of others. A good teacherforms a belief about the knowledge of their student, asks clar-ifying questions, and gives instructions or explanations to tryto induce a target concept in the student’s mind. We proposePartially Observable Markov Decision Processes (POMDPs)as a model of intuitive human teaching. According to this ac-count, teachers make pedagogical decisions with uncertaintyabout the knowledge state of their student. In two behavioralexperiments, human participants were tasked with balancingassessments (asking questions) and instructions to help teach astudent to build a tower of colored blocks. Human behavior inthe task was compared to the performance of a computerizedteaching algorithm optimized to solve the equivalent POMDP.Our results show that humans favor asking questions and estab-lishing common ground during teaching even at an economiccost and increase question asking as uncertainty grows.

The theory of Enactive Inference was proposed by Karl Friston and his colleagues to explain how the brain infers knowledge about the world through the subject's interactive experiences. Sensorimotor states induce perturbations in neural activity, and the brain infers hypothetical causes in the world that may explain these perturbations. This article aims to reconcile this neuroscience theory with computer science and artificial-intelligence theories wherein artificial agents receive input data derived from the environment's state and infer internal data structures used to guide decisions. Two critical challenges arise in both the agent's active role and the inference algorithm's scalability as the environment's complexity increases. To address these challenges, we formalize artificial enactive inference through a new Spatial Enactive Markov Decision Process (SEMDP) model. This model rests on low-level control loops enacted in a three-dimensional Euclidean space containing objects. Based on the SEMDP, we present a proof-of-concept cognitive architecture and an experiment to demonstrate the transcription of the theory of enactive inference into the domain of artificial intelligence and robotics. [ABSTRACT FROM AUTHOR]

In the theory of Partially Observed Markov Decision Processes (POMDPs), existence of optimal policies have in general been established via converting the original partially observed stochastic control problem to a fully observed one on the belief space, leading to a belief-MDP. However, computing an optimal policy for this fully observed model, and so for the original POMDP, using classical dynamic or linear programming methods is challenging even if the original system has finite state and action spaces, since the state space of the fully observed belief-MDP model is always uncountable. Furthermore, there exist very few rigorous value function approximation and optimal policy approximation results, as regularity conditions needed often require a tedious study involving the spaces of probability measures leading to properties such as Feller continuity. In this paper, we study a planning problem for POMDPs where the system dynamics and measurement channel model are assumed to be known. We construct an approximate belief model by discretizing the belief space using only finite window information variables. We then find optimal policies for the approximate model and we rigorously establish near optimality of the constructed finite window control policies in POMDPs under mild non-linear filter stability conditions and the assumption that the measurement and action sets are finite (and the state space is real vector valued). We also establish a rate of convergence result which relates the finite window memory size and the approximation error bound, where the rate of convergence is exponential under explicit and testable exponential filter stability conditions. While there exist many experimental results and few rigorous asymptotic convergence results, an explicit rate of convergence result is new in the literature, to our knowledge. [ABSTRACT FROM AUTHOR]

Given the high energy demands for heating and cooling, and the currently limited use of renewable sources, there is a pressing need for efficient and economically viable geothermal development. However, the success of new geothermal reservoir projects hinges on numerous uncertain geological and economic factors. Prior to development, the project uncertainty can be reduced by performing costly data acquisition campaigns. The central question in these campaigns is: which data should be acquired in which order to determine the viability of the proposed project? Traditional methods based on value of information and other heuristics are insufficient for assessing large-scale multi-well geothermal projects. Our approach reformulates geothermal assessment as a partially observable Markov decision process (POMDP), employing algorithmic decision-making techniques to devise an approximately optimal data acquisition strategy. Applied to a real-world low-enthalpy geothermal project in Austria, our methodology increased the expected net present value of the project by nearly 30% over baseline methods (including human experts) by minimizing the risk of developing a non-profitable project. This advancement not only promises a more efficient path towards large-scale geothermal energy production but also sets a precedent for applying sophisticated decision-making frameworks in renewable energy projects. [ABSTRACT FROM AUTHOR]

We introduce and study Regular Decision Processes (RDPs), a new, compact model for domains with non-Markovian dynamics and rewards, in which the dependence on the past is regular, in the language theoretic sense. RDPs are an intermediate model between MDPs and POMDPs. They generalize k -order MDPs and can be viewed as a POMDP in which the hidden state is a regular function of the entire history. In factored RDPs, transition and reward functions are specified using formulas in linear temporal logics over finite traces, or using regular expressions. This allows specifying complex dependence on the past using intuitive and compact formulas, and building models of partially observable domains without specifying an underlying state space. [ABSTRACT FROM AUTHOR]

Robot sequential decision-making in the real world is a challenge because it requires the robots to simultaneously reason about the current world state and dynamics, while planning actions to accomplish complex tasks. On the one hand, declarative languages and reasoning algorithms support representing and reasoning with commonsense knowledge. But these algorithms are not good at planning actions toward maximizing cumulative reward over a long, unspecified horizon. On the other hand, probabilistic planning frameworks, such as Markov decision processes (MDPs) and partially observable MDPs (POMDPs), support planning to achieve long-term goals under uncertainty. But they are ill-equipped to represent or reason about knowledge that is not directly related to actions. In this article, we present an algorithm, called iCORPP, to simultaneously estimate the current world state, reason about world dynamics, and construct task-oriented controllers. In this process, robot decision-making problems are decomposed into two interdependent (smaller) subproblems that focus on reasoning to "understand the world" and planning to "achieve the goal" respectively. The developed algorithm has been implemented and evaluated both in simulation and on real robots using everyday service tasks, such as indoor navigation, and dialog management. Results show significant improvements in scalability, efficiency, and adaptiveness, compared to competitive baselines including handcrafted action policies. • This article formally introduces the Integrated Reasoning and Planning (IRP) problem for robots. An IRP problem has a factored state space that is specified by a set of endogenous and exogenous variables. • This article introduces a sequential decision-making algorithm, called Interleaved Commonsense Reasoning and Probabilistic Planning (iCORPP), for addressing IRP problems. • This article presents systematic evaluations of iCORPP using two tasks of mobile robot navigation, and spoken dialog systems, as demonstrated on a real robot. • This article builds on our previous research that appeared in two conference papers (Zhang and Stone, 2015; Zhang et al., 2017). This article unifies their terminology, problem statements, and algorithms. • Compared to our prior work, this article introduces a new problem statement in Section 4.1, which covers the problems addressed in both conference papers. • To address the IRP problem, we have reformulated the iCORPP algorithm (Section 4.2) into a novel form that includes the three key steps of "logical reasoning," "probabilistic reasoning over world states," and "probabilistic reasoning about world dynamics." [ABSTRACT FROM AUTHOR]

Highlights • aPOMDP controls an agent's actions to maintain the user in maximum value states. • Three reward functions based on state value and entropy are proposed and compared. • Online learning of the transition matrix T is done through a knowledge update step. • User stays in most valuable states up to 71% of the time, lowering T entropy to 0.7. • User tests show that the technique is transferable to real scenarios with robots. Abstract In this work we present α POMDP: a User-Adaptive Decision-Making technique for social robots. This technique is based on the classical POMDP formulation which we extend with novel aspects inspired by Reward Shaping and Model-Based Reinforcement Learning. Our technique innovates in two main ways: by applying a novel set of rewarding schemes based on the state of the user and by employing a novel execution loop that enables the system to learn the impact of its actions on the user on-the-fly. Our technique has been tested with multiple POMDP solvers and reward formulations in simulations and with real users through the GrowMu social robot. Results show that our technique is able to correctly decide which actions to take, maintaining the user in positive states which interacting with the robot and methodically exploring and learning their characteristics, activities and behaviors. [ABSTRACT FROM AUTHOR]

ACSM (Hayashida et al., 2014) consists of a method of discerning the aliased states in a POMDP (Partially Observable Markov Decision Process) which is one of Markov decision process such that an agent observes local information about the environment, and choosing the appropriate action based on the internal memory and the sensory information which an agent obtains from the environment. Though ACSM achieves the highest performance in the existing methods based on classifier systems, it requires a huge number of memories for the internal memories, and spends long time for some large scaled problems. This paper improves a classifier system, ACSM (Anticipatory Classifier System with Memory) focused on the process of learning of ACSM, and the aim of this paper is to make the system more efficient. The improved method is named ACSMr in this paper, and some numerical experiments using 5 kinds of maze problems which are well used as benchmark problems for POMDPs are executed. ACSMr achieves greater experimental result than the existing classifier systems for the maze problems. [ABSTRACT FROM AUTHOR]

Sensor control is a challenging issue in the field of multi-target tracking. It involves multi-target state estimation and the optimal control of the sensor. To maximize the overall utility of the surveillance system, we propose a dual sensor control scheme. This work is formulated in the framework of partially observed Markov decision processes (POMDPs) with Mahler’s finite set statistics (FISST). To evaluate the performance associated with each control action, a key element is to design an appropriate metric. From a task-driven perspective, we utilize a metric to minimize the posterior distance between the sensor and the target. This distance-related metric promotes the design of a dual sensor control scheme. Moreover, we introduce a metric to maximize the predicted average probability of detection, which will improve the efficiency by avoiding unnecessary update processes. Simulation results indicate that the performance of the proposed algorithm is significantly superior to the existing methods.

We exhibit that a robot shows strategic behaviors for overcoming uncertainty of information in navigation tasks by a modification of the core formula invalue method. The new formula biases the calculation so as to give a priority, the decision-making to an important part of the state space.value method with the modified formula is named as probabilistic flow control (PFC) method. We apply PFC method to a simulated simple task of a mobile robot. In the task, the robot with PFC method shows tricky behaviors that compensate the uncertainty of state information. [ABSTRACT FROM AUTHOR]

We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [ 0 , 1 ] is associated with every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) a quantitative constraint defines the set of paths where the payoff is at least a given threshold λ 1 ∈ ( 0 , 1 ] ; and (ii) a qualitative constraint which is a special case of the quantitative constraint with λ 1 = 1 . We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraints are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We also present a prototype implementation of our EXPTIME algorithm and experimental results on several examples. [ABSTRACT FROM AUTHOR]

• Groundwater remediation planning and decision problem formulated as a partially observable Markov decision process (POMDP). • Comparison between POMDP and the conventional state-of-the-art optimization approaches, such as one-shot optimization and model predictive control (closed loop) optimization. • DESPOT, a state-of-the-art POMDP solver, outperforms optimization solution methods using PSO and hand-crafted heuristic solutions. • Optimizing the trade-off between information gathering and the performance of possible future scenarios via POMDP formulation. • Importance of belief updates, also known as inversion problems or history matching, in groundwater problems. Groundwater contamination causes significant groundwater supply risks that severely affect humans and livestock, especially in the era of climate change. Consequently, the need to develop and optimize remediation strategies such as pump and treat is indispensable. An effective and efficient strategy can reduce the spread of contaminants and cost of clean-up. However, developing such a strategy is challenging due to the inherent uncertainty and sequential nature of the problem. For example, taking actions such as drilling wells is interwoven with information gathering over time. In this paper, we formulate the groundwater remediation planning and decision problem as a partially observable Markov decision process (POMDP). A POMDP formulation allows planning by optimizing the trade-off between information gathering and the performance of possible future scenarios. We use a state-of-the-art POMDP solver called DESPOT for planning remediation strategies. The results show that DESPOT can yield much better remediation strategies than hand crafted heuristics and optimization methods. The superior performance of DESPOT is due to the incorporation of both previous information and future reward into the current decision. We also demonstrate the robustness of the POMDP formulation to measurement error. [ABSTRACT FROM AUTHOR]

This paper improves a classifier system, ACS (Anticipatory Classifier System). The suggested classifier system is named ACSM (ACS with Memory) which consists of a method of discerning the aliased states in a POMDP (Partially Observable Markov Decision Process), and choosing the proper action based on the internal memory and the sensory information around the agent. A POMDP is one of Markov decision process such that an agent observes local information about the environment. This paper executes some numerical experiments using eight kinds of maze problems which are well used as benchmark problems for POMDPs. ACSM achieves greater experimental result than the existing classifier systems for the maze problems. [ABSTRACT FROM AUTHOR]

Structural uncertainty arises when key features of the behavior of a system are not well understood. Observational uncertainty arises when key variables in a system are not directly observed. Both types of uncertainty lead to problems for standard dynamic optimization approaches. The replacement of uncertainties by belief distributions over those uncertainties is one approach to addressing the problem. The use of this and other approaches are reviewed, with an emphasis on applications to environmental and resource management problems. [ABSTRACT FROM AUTHOR]

To improve the natural human-avoidance skills of service robots, a human motion predictive navigation method is proposed, namely PN-POMDP. A humanrobot motion co-occurrence estimation algorithm is proposed which incorporates long-term and short-term human motion prediction. To improve the reliability of probabilistic and predictive navigation, the POMDP model is utilized to generate navigation control policies through theoretically optimal decisions. A layered motion control structure is proposed that combines global path planning and reactive avoidance. Multiple comity policies are integrated with a decision-making module that generates efficient and human-compliant navigational behaviours for robots. Experimental results illustrate the effectiveness and reliability of the predictive navigation method. [ABSTRACT FROM AUTHOR]

This paper presents a decision-theoretic approach to problems that require accurate placement of a robot relative to an object of known shape, such as grasping for assembly or tool use. The decision process is applied to a robot hand with tactile sensors, to localize the object on a table and ultimately achieve a target placement by selecting among a parameterized set of grasping and information-gathering trajectories. The process is demonstrated in simulation and on a real robot. This work has been previously presented in Hsiao et al. (Workshop on Algorithmic Foundations of Robotics (WAFR), ; Robotics Science and Systems (RSS), ) and Hsiao (Relatively robust grasping, Ph.D. thesis, Massachusetts Institute of Technology, ). [ABSTRACT FROM AUTHOR]

A central problem in artificial intelligence is to choose actions to maximize reward in a partially observable, uncertain environment. To do so, we must learn an accurate environment model, and then plan to maximize reward. Unfortunately, learning algorithms often recover a model that is too inaccurate to support planning or too large and complex for planning to succeed; or they require excessive prior domain knowledge or fail to provide guarantees such as statistical consistency. To address this gap, we propose a novel algorithm which provably learns a compact, accurate model directly from sequences of action-observation pairs. We then evaluate the learner by closing the loop from observations to actions. In more detail, we present a spectral algorithm for learning a predictive state representation (PSR), and evaluate it in a simulated, vision-based mobile robot planning task, showing that the learned PSR captures the essential features of the environment and enables successful and efficient planning. Our algorithm has several benefits which have not appeared together in any previous PSR learner: it is computationally efficient and statistically consistent; it handles high-dimensional observations and long time horizons; and, our close-the-loop experiments provide an end-to-end practical test. [ABSTRACT FROM AUTHOR]

POMDPs and their decentralized multiagent counterparts, DEC-POMDPs, offer a rich framework for sequential decision making under uncertainty. Their high computational complexity, however, presents an important research challenge. One way to address the intractable memory requirements of current algorithms is based on representing agent policies as finite-state controllers. Using this representation, we propose a new approach that formulates the problem as a nonlinear program, which defines an optimal policy of a desired size for each agent. This new formulation allows a wide range of powerful nonlinear programming algorithms to be used to solve POMDPs and DEC-POMDPs. Although solving the NLP optimally is often intractable, the results we obtain using an off-the-shelf optimization method are competitive with state-of-the-art POMDP algorithms and outperform state-of-the-art DEC-POMDP algorithms. Our approach is easy to implement and it opens up promising research directions for solving POMDPs and DEC-POMDPs using nonlinear programming methods. [ABSTRACT FROM AUTHOR]

This paper considers the problem of autonomous robot navigation in dynamic and congested environments. The predictive navigation paradigm is proposed where probabilistic planning is integrated with obstacle avoidance along with future motion prediction of humans and/or other obstacles. Predictive navigation is performed in a global manner with the use of a hierarchical Partially Observable Markov Decision Process (POMDP) that can be solved on-line at each time step and provides the actual actions the robot performs. Obstacle avoidance is performed within the predictive navigation model with a novel approach by deciding paths to the goal position that are not obstructed by other moving objects movement with the use of future motion prediction and by enabling the robot to increase or decrease its speed of movement or by performing detours. The robot is able to decide which obstacle avoidance behavior is optimal in each case within the unified navigation model employed. [ABSTRACT FROM AUTHOR]

This paper examines the problem of locating a mobile, nonadversarial target in an indoor environment using multiple robotic searchers. One way to formulate this problem is to assume a known environment and choose searcher paths most likely to intersect with the path taken by the target. We refer to this as the multi-robot efficient search path planning (MESPP) problem. Such path planning problems are NP-hard, and optimal solutions typically scale exponentially in the number of searchers. We present an approximation algorithm that utilizes finite-horizon planning and implicit coordination to achieve linear scalability in the number of searchers. We prove that solving the MESPP problem requires maximizing a nondecreasing, submodular objective function, which leads to theoretical bounds on the performance of our approximation algorithm. We extend our analysis by considering the scenario where searchers are given noisy non-line-of-sight ranging measurements to the target. For this scenario, we derive and integrate online Bayesian measurement updating into our framework. We demonstrate the performance of our framework in two large-scale simulated environments, and we further validate our results using data from a novel ultra-wideband ranging sensor. Finally, we provide an analysis that demonstrates the relationship between MESPP and the intuitive average capture time metric. Results show that our proposed linearly scalable approximation algorithm generates searcher paths that are competitive with those generated by exponential algorithms. [ABSTRACT FROM AUTHOR]

Solving partially observable Markov decision processes (POMDPs) is a complex task that is often intractable. This paper examines the problem of finding an optimal policy for POMDPs. While a lot of effort has been made to develop algorithms to solve POMDPs, the question of automatically finding good low-dimensional spaces in multi-agent co-operative learning domains has not been explored thoroughly. To identify this question, an online algorithm CMEAS is presented to improve the POMDP model. This algorithm is based on a look-ahead search to find the best action to execute at each cycle. Thus the overwhelming complexity of computing a policy for each possible situation is avoided. A series of simulations demonstrate this good strategy and performance of the proposed algorithm when multiple agents co-operate to find an optimal policy for POMDPs. [ABSTRACT FROM AUTHOR]

Vera and Simon [Cognitive Science, 17 (1993) 117] complain that the situational approach to cognition is insufficiently operationalized. This paper presents an interpreted system of diagrams that permit descriptions of tasks in both symbolic and situative terms, allowing differences to be operationally defined. It is argued that the basic language for describing psychological phenomena, shared by both behavioral and cognitive approaches, that of stimulus and response, is not adequate for the situational approach. Two examples, one drawn from published research in animal learning and one illustrating a re-analysis of standard tasks used in studies of problem solving, demonstrate differences between characterizing tasks in traditional stimulus–response terms as opposed to characterizing tasks in terms of situations, deeds, and observations. Connections are made to Reinforcement Learning and the study of Partially Observable Markov Decision Processes (POMDPs). [Copyright &y& Elsevier]

Crowdsourcing receives massive vote information from non-expert workers, for finishing tasks that can hardly be handled by current technology of machine intelligence. Massive vote information and non-expert workers bring serious issues of labor costs and the efficiency of crowdsourcing. This paper focuses on the tasks, classifying objects in images or videos into a set of given candidates by letting workers vote on a set of options that characterize these candidates. Designing a good asking strategy, i.e., setting up the order of presenting the options to a worker and asking the worker whether an option is true or false, is one starting point to save labor costs and enhance efficiency of deciding the correct answer from the candidates. We propose the problem of determining the time steps of vote collection before stopping to set up the asking strategy. In terms of this problem, we establish a single-step collection based partially observable Markov decision process (POMDP) to analyze how a vote influences the whole system, for instance, influences the belief over each option. Formally define the multistep collection problem as the timed decision (TD) problem. We propose the MC-EVA algorithm based on Monte Carlo sampling to solve the TD problem. Evaluate the MC-EVA algorithm over three simple but typical cases and a real-world Galaxy Zoo 2 project. Experiments show MC-EVA's great superiority in runtime over the state-of-the-art single-step collection algorithm, and its superiority in effectiveness than other multistep collection algorithms; show its labor cost saving and enhanced efficiency with the use of calculated asking strategies. [ABSTRACT FROM AUTHOR]

Sensor control is a challenging issue in the field of multi-target tracking. It involves multi-target state estimation and the optimal control of the sensor. To maximize the overall utility of the surveillance system, we propose a dual sensor control scheme. This work is formulated in the framework of partially observed Markov decision processes (POMDPs) with Mahler’s finite set statistics (FISST). To evaluate the performance associated with each control action, a key element is to design an appropriate metric. From a task-driven perspective, we utilize a metric to minimize the posterior distance between the sensor and the target. This distance-related metric promotes the design of a dual sensor control scheme. Moreover, we introduce a metric to maximize the predicted average probability of detection, which will improve the efficiency by avoiding unnecessary update processes. Simulation results indicate that the performance of the proposed algorithm is significantly superior to the existing methods. [ABSTRACT FROM AUTHOR]