Competence in interacting with the spatial world, the ability to move around an obstacle, or reach for a desired object, is one of the most immediate needs of any agent existing in such a world. For my thesis work, I am extending a largely-symbolic AI system, the Soar cognitive architecture (Laird, 2008), to better handle spatial problems. A key aspect in the design of Soar is a commitment to generality: the goal of the architecture is to be able to solve the same breadth problems humans are able to solve. In addition, Soar is a psychologically-inspired architecture: a second goal is to solve problems in a manner similar to humans. These goals are reflected in the design of the existing architecture, and must be reflected in the design of any extension to it. Systems for spatial reasoning exist, but they are typically defined for limited domains, and in isolation from a comprehensive intelligent system. My approach to the problem derives from work in diagrammatic reasoning and systems exploring mental imagery. The system augments symbolic working memory in Soar with short-term and long-term memories specialized for spatial information. Reasoning is then a process of manipulating both symbolic and lower-level perceptual data.

Multi-agent pathfinding is a challenging problem with many important real-life applications. Despite its completeness and solution solution optimality guarantees, a global search such as centralised A* has little practical value due to its exponential state space. Scalability to larger problems has been achieved with decentralized approaches, which decompose an initial problem into a series of searches. Even though their CPU and memory requirements are significantly lower, existing decentralized methods are incomplete and provide no criteria to distinguish between problems that can successfully be solved and problems where such algorithms fail. Further, no guarantees are given with respect to the running time, the memory requirements, and the quality of the computed solutions. Addressing such limitations is the central motivation for our recent and current work on identifying a tractable class of problems and developing an algorithm that is complete on this class of problems, with guarantees of low-polynomial running time, memory requirements and solution length.

A* is the optimal algorithm for finding optimal solutions to heuristic search problems. Given the same amount of information, no search can expand fewer nodes. Many applications of heuristic search only require that we find solutions of reasonable quality or in a reasonable amount of time, where reasonable is defined by the needs of a user. My doctoral work will address these problems by developing new bounded suboptimal algorithms which perform better than the previous approaches. I will show that anytime searches can incorporate these new algorithms to improve their own performance. I will demonstrate that anytime search is not the correct approach when a deadline is known at the beginning of the search, and introduce deadline-aware search algorithms that address this setting directly.

Developing scalable and adaptive algorithms for reasoning and acting under uncertainty is an important area in artificial Intelligence. A large subclass of these problems may be formulated as Markov decision processes and are typically solved by Approximate Dynamic Programming (ADP). While ADP has recently gained traction in many domains, the successful applications often require extensive parameter tuning in order to obtain a sufficiently small approximation error. The goal of my thesis is to develop ADP methods that reduce the need for extensive tuning. I particularly focus on Approximate Linear Programming (ALP), a type of ADP. ALP has a number of theoretical advantages over other approximate dynamic programming methods, but in practice it suffers from the same performance issues as other ADP algorithms. These issues are mostly due to a large approximation error. I analyze the approximation error and propose methods for mitigating it. First, I examine various linear program formulations and their effect on the approximation error. ALP, like other ADP methods, involves sampling, which often significantly contributes to degradation in the solution quality. I analyze the sampling error and propose methods for minimizing it. Finally, the representation used in the approximation plays a crucial role in the performance. I therefore describe approaches to automatically tuning the representation in some common settings.

As computational learning agents move into domains that incur real costs (e.g., autonomous driving or financial investment), it will be necessary to learn good policies without numerous high-cost learning trials. One promising approach to reducing sample complexity of learning a task is knowledge transfer from humans to agents. Ideally, methods of transfer should be accessible to anyone with task knowledge, regardless of that person's expertise in programming and AI. This thesis statement focuses on allowing a human trainer to interactively shape an agent's policy via reinforcement signals.

In large, distributed sensor web systems, allocating resources to complex user tasks presents significant challenges. Sensor web users and their desired tasks have differing importance in the sensor web, so designing a multi-agent framework to yield allocations that are both fair and efficient (high utility) is a challenging research problem. With complex, hierarchically-decomposable tasks, individual subtasks could potentially be assigned to a number of agents (e.g., when there is overlap in sensor or data processing capability among constituent sensor networks). Efficient allocation of subtasks within the proposed multi-agent framework presents additional challenges. Both of these research problems are further compounded by the dynamic nature of the sensor web, in which both desired tasks and resource availability change significantly with time and environmental conditions. This paper presents an overview of these research challenges and a solution approach employing broker agents in a novel variation of the contract net protocol (CNP) for fair and efficient allocation of complex tasks.

This paper describes an approach to scheduling under uncertainty that achieves scalability through a coupling of deterministic and probabilistic reasoning. A class of oversubscribed scheduling problems is considered where the goal is to maximize the reward earned by a team of agents in a distributed execution environment. There is uncertainty in both the duration and outcomes of executed activities, and activities are subject to deadlines. To ensure scalability, the approach takes as its starting point an initial deterministic schedule for the agents, computed using expected duration reasoning. This initial agent schedule is probabilistically analyzed to find likely points of failure, and then selectively strengthened based on this analysis. Experimental results obtained in a multi-agent simulation environment demonstrate that coupling probabilistic and deterministic reasoning in this way results in significantly higher rewards than are achieved by relying on deterministic reasoning alone. In the future, the approach will be extended to include probability-driven meta-level management of execution.

Many fields have a need to build representative or predictive models from a number of unique individuals who each can contribute their experience and beliefs to the whole. For instance, intelligence agencies may wish to build a model from a number of experts to analyze potential terrorist attacks. In addition, a sociological survey may want a model representing the beliefs of cultural or political groups. However, challenges remain that have limited the success of merging opinions to form consensus models. Our research in progress presents a new approach to combine, or aggregate the beliefs of many individuals using graphical models. Existing Bayesian belief aggregation methods utilize an opinion pool function to find a single consensus on a given probability distribution. These opinion pool functions have many theoretical problems including breaking several assumptions for Bayesian reasoning. More practically, existing opinion pool functions do not represent reality well, especially in cases of diverse opinions.

Many complex real-world systems can be modeled using a graphical representation such as a constraint network. If structure can be exploited, many challenging computational tasks can have good typical-case runtimes even if they are theoretically intractable in general. This paper reports on some early experiments in a PhD-level research agenda. We report on a novel constraint network generator for random constraint networks that have a scale-free macrostructure. This scale-free generator is based on the well known Barabasi-Albert preferential attachment model. We show that scale-free constraint networks exhibit interesting phase transition behaviours which have not been seen for other problem classes studied so far.

Deadline pressures, unexpected events, and combinatorial numbers of possible courses of action often lead a person to decide which activity she will begin next without considering a full enumeration of possible schedules, and thus, without a full awareness of the implications that her choice will have on the rest of her day's schedule. Furthermore, people suffering from cognitive impairments may lack the abilities to perform such reasoning in the first place. The goal of my thesis is to develop foundational technologies for computational agents that augment the abilities of people who face the above challenges to reason about the implications of scheduling. In particular, I develop, integrate, and evaluate new techniques for solving multi-agent Hybrid Scheduling Problems, which support coordinated activity selection and scheduling for human users.