In this article, we develop a framework to obtain graph abstractions for decision-making where the abstractions emerge as a function of the agent’s available resources. We discuss the connection of the proposed approach with information-theoretic signal compression and formulate a novel optimization problem to obtain tree-based abstractions that are a function of the agent’s computational resources. The structural properties of the new problem are discussed in detail and two algorithmic approaches are proposed. We discuss the quality of, and prove relationships between, the solutions obtained by the two proposed algorithms. The framework is applied to a variety of environments to obtain hierarchical abstractions.
Human Swarm Interaction (HSI) is a new field which relates to the effective control of robotic swarms by human operators. The iterature has shown that the control of swarms can become quite complicated. On the other hand, Brain Machine Interfaces (BMI) can offer intuitive control in a plethora of applications where other interfaces alone (e.g. joysticks) are inadequate or impractical, e.g. for people with motor disabilities. There are multiple types of BMI, but most of them rely on the analysis of ElectroEncephaloGraphic (EEG) signals. The authors have previously shown that swarm behaviors elicit specific brain activity on human subjects that observe them. Motivated by this result, in this work, we present preliminary results of a hybrid BMI that combines information from the brain and an external device. An algorithm for extracting information from the frequency domain of EEG signals that allows integration with the manual task of using a joystick is presented. The hybrid interface shows high accuracy and robustness when used as a brain-robot interface. Moreover, it allows for continuous control variables extracted from the EEG signals. Finally, its efficacy is proven across multiple subjects, while its performance is also demonstrated in the real-time control of a swarm of quadrotors.
26 July 2021 in IEEE Robotics and Automation Letters
In this paper, we develop a framework for path-planning on abstractions that are not provided to the agent a priori but instead emerge as a function of the available computational resources. We show how a path-planning problem in an environment can be systematically approximated by solving a sequence of easier-to-solve problems on abstractions of the original space. The properties of the problem are analyzed, and a number of theoretical results are presented and discussed. A numerical example is presented to show the utility of the approach and to corroborate the theoretical findings. We conclude by providing a discussion detailing the connections of the proposed approach to anytime algorithms and bounded rationality.
In this semi-tutorial paper, we first review the information-theoretic approach to account for the computational costs incurred during the search for optimal actions in a sequential decision-making problem. The traditional (MDP) framework ignores computational limitations while searching for optimal policies, essentially assuming that the acting agent is perfectly rational and aims for exact optimality. Using the free-energy, a variational principle is introduced that accounts not only for the value of a policy alone, but also considers the cost of finding this optimal policy. The solution of the variational equations arising from this formulation can be obtained using familiar Bellman-like value iterations from dynamic programming (DP) and the Blahut-Arimoto (BA) algorithm from rate distortion theory. Finally, we demonstrate the utility of the approach for generating hierarchies of state abstractions that can be used to best exploit the available computational resources. A numerical example showcases these concepts for a path-planning problem in a grid world environment.
In this paper, a generalized information-theoretic framework for the emergence of multi-resolution hierarchical tree abstractions is developed. By leveraging ideas from information-theoretic signal encoding with side information, this paper develops a tree search problem which considers the generation of multi-resolution tree abstractions when there are multiple sources of relevant and irrelevant, or possibly confidential, information. We rigorously formulate an information-theoretic driven tree abstraction problem and discuss its connections with information-theoretic privacy and resource-limited systems. The problem structure is investigated and a novel algorithm, called G-tree search, is proposed. The proposed algorithm is analyzed and a number of theoretical results are established, including the optimally of the G-tree search algorithm. To demonstrate the utility of the proposed framework, we apply our method to a real-world example and provide a discussion of the results from the viewpoint of designing hierarchical abstractions for autonomous systems.
The majority of work in pursuit-evasion games assumes perfectly rational players who are omnipotent and have complete knowledge of the environment and the capabilities of other agents and, consequently, are correct in their assumption of the game that is played. This is rarely the case in practice. More often than not, the players have different knowledge about the environment either because of sensing limitations or because of prior experience. In this paper, we wish to relax this assumption and consider pursuit-evasion games in a stochastic setting, where the players involved in the game have different perspectives regarding the transition probabilities that govern the world dynamics. We show the existence of a (Nash) equilibrium in this setting and discuss the computational aspects obtaining such an equilibrium. We also investigate a relaxation of this problem employing the notion of correlated equilibria. Finally, we demonstrate the approach using a grid-world example with two players in the presence of obstacles.