# Decision Theory and Motion Planning

Motion planning and decision making are at the core of Robotics and A.I. In theory, these problems can be solved using optimal control or dynamic programming. However, computational cost for solving many real world problems is prohibitively high and is exacerbated by the “curse of dimensionality”. Randomized sampling-based methods (like RRT*) ameliorate this problem by avoiding apriori griding of the environment and incrementally building a graph online. On the other hand, deterministic search algorithms (such as A*) can be augmented with intelligent abstractions to speed up their performance, and decision theory can borrow ideas from information theory to model agents that are resource-aware. Current research in this area lies at the intersection of A.I, machine learning, optimal control and information theory.

### Sampling-based Algorithms for Optimal Motion Planning

Motion planning and trajectory generation problems are at the at the core of all autonomous and robotic systems. Although – at least in theory – such problems can be solved using optimal control or dynamic programming, the computational complexity for realizing these solutions is still prohibitive for many real-life problems, especially for high-dimensional systems. Recently, randomized algorithms have been proposed, which promise to remedy the “curse of dimensionality” associated with more traditional, deterministic methods.

### Information Theoretic Abstractions and Decision Making

Markov Decision Processes (MDP) is the standard framework for optimal sequential decision making under uncertainty. However, this framework assumes that the decision maker, customary referred to as the “agent,” is perfectly rational. That is, the agent is assumed to have unlimited computational and/or time resources to process all information and compute the optimal solution unhindered. In many practical applications this is a strong and often unrealistic assumption. For example, biological systems are adaptive in nature and excel at finding solutions to complex problems that may not be globally optimal but are “good enough” given the constraints and/or available sensory information.

With this motivation, we seek to introduce constraints (computational and otherwise) to the decision process to model agents that do not have access to unlimited resources, and hence will select actions that are not optimal in the traditional sense of maximizing value or utility, but rather in the sense of maximizing (expected) value or utility for a given processing cost.

### Multi-Agent Multi-Scale Path Planning

Although complete knowledge of the environment is necessary to plan an optimal solution for given task, the information about the world in which a planning agent is to plan is rarely entirely known. More likely, the agent has only a glimpse of the world abstracted away from the current state and time. This idea has led many researchers to wonder how to abstract the search space in an efficient and meaningful way. Since the early days of AI, a hierarchical abstraction of a transition system has been recognized as a crucial tool for planning in complex environments and long decision horizons.

## Game Theory

Game theory provides for a mathematical framework to study optimal decision making in multi-agent decision making problems. It provides a rich framework to study situations ranging from competitive and strategic encounters between agents to cooperative, team-game, scenarios. However, research within this field has been mainly concerned with cases where each player/agent has perfect and symmetric knowledge of the environment or understanding of the game at hand. In our research, we seek to progressively relax these assumptions, and to model real-world scenarios where agents may not all be created equal - that is, not all have the same ability or understanding of the evolution of the system dynamics, etc. We employ results from machine learning, theoretical game theory and optimization theory to model, solve and establish theoretical results from this new field of research.

### Level-K Thinking for Pursuit-Evasion Games

Pursuit-Evasion Game (PEG) models a family of problems in which one group of agents attempt to track down members of another group in an environment. This type of problem has a variety of applications in military and civil fields, for example, an adversary aerial combat or a surveillance/tracking mission. Over the past decades, people strive to solve for the equilibrium of such games, either Nash equilibrium or the correlated equilibrium, where all the agents are assumed to be totally rational. However, the equilibrium is generally hard to solve and may require a significant amount of computational time. In reality, agents (both autonomous agents and humans) only have limited computational capacity, limited information and limited time. As a result, critiques of the perfect rationality assumption in the notion of equilibrium arose, and people want to introduce the idea of bounded rationality.

### Pursuit-Evasion Games under Lack of Common Knowledge

Pursuit-evasion games have traditionally been studied under the assumption that both player have an identical understanding of the environment in which they operate. However this is rarely true in practice. Instead, players form their own understanding of the dynamics of the world. This discrepancy in the understanding of the evolution of the system may arise due to sensing limitations or because of the agent's prior experience or may also be due to deception, measurement capability of the agent or erroneous modeling assumptions of the environment.

### Min-Max Differential Dynamic Programming

Design of a robust controller formalized as a $\mathcal{H}_\infty$ control problem has been successfully extended with min-max game theoretic formulation to cope with model uncertainty and external disturbances. Such attempts were derived in the context of the small gain theorem to ensure the system stability under unstructured perturbations, and recently applied to dynamic programming algorithms to solve for the locally optimal trajectory with robustness guaranteed.