Multi-agent path planning is a challenging problem with numerous real-life applications, including robotics, logistics, military operations planning, disaster rescue, and computer games. We look at navigating large numbers of mobile units to their targets on navigation graphs such as grid maps. The size of problems examined is significantly larger than can be handled using optimal multi-agent pathfinding algorithms in practice. We introduced MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. MAPP and its extended versions are complete on well specified and tractably testable classes of problems. They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Experiments on realistic game grid maps, with uniformly randomly generated start and target locations for each unit, show MAPP as a state-of-the-art multi-agent pathfinding algorithm in terms of scalability and success ratio (i.e., percentage of solved units). Even on challenging scenarios with 2000 units, MAPP solves 92% to 99.7% of units. FAR and WHCA*, two fast but incomplete algorithms that were previously state-of-the-art in terms of scalability, solve as few as 17.5% and 12.3% of these problems. The quality of MAPP's solutions is empirically analyzed using multiple quality criteria: total travel distance, makespan, and sum of actions (including move and wait actions). MAPP is competitive in terms of solution quality and speed with FAR and WHCA*. MAPP further provides the formal characterizations that FAR and WHCA* lack, on problems it can solve as well as low-polynomial upper bounds on the resources required. As optimal algorithms have limited scalability, we evaluated the solution quality of suboptimal algorithms using lower bounds of optimal values. We showed that MAPP's solutions have a reasonable quality. For example, MAPP's total travel distance is on average 19% longer than a lower bound on the optimal value.

Planning under uncertainty is one of the most general and hardest problems considered in the area of planning. Uncertainty can take the form of incomplete information, wrong information, multiple action outcomes, and varying action durations. My doctoral thesis concentrates on planning with incomplete knowledge and multiple action outcomes, specifically conformant planning and contingent planning. These problems have attracted the attention of many researchers, resulting in numerous sophisticated planners of different approaches. However, those planners cannot scale up well on the size of problems, mostly due to the representation methods employed in the planners. The doctoral research work provides a systematic methodology for dealing with planning under uncertainty, focusing on the representation of belief states that can be used in a forward search paradigm in the belief space for solutions. A good representation should be compact so that a planner implementing it can perform and scale up well as the larger the formulae, the more the computation and the more the memory consumption (i.e., the slower the system and the less the scalability). On the other hand, it should also have properties that allow for definition of an efficient transition function for computing successor belief states, e.g., checking satisfaction in a DNF formula is easy. Defining a direct complete transition function in presence of incomplete information for a general representation, other than the belief state, is particularly hard due to conditional action effects. To address this, I propose a generic abstract algorithm, called GAA, for defining such function given an arbitrary representation. Using the GAA algorithm, my doctoral thesis investigates the properties of different logical formulae and their applicability in planning under uncertainty as a belief state representation. The results obtained so far are very promissing as the research work developed several highly competitive planners which outperform other state-of-the-art planners in most benchmarks available in the literature.

Heuristic search is a central component of many important applications in AI including automated planning.  While we can find  optimal solutions to heuristic search problems, doing so may take hours or days. For practical applications, this is unacceptably slow, and we must rely on algorithms which find solutions of high, but not optimal, quality or ones which bound the time used directly. In my dissertation, I present and analyze algorithms for the following settings: quality bounded heuristic search and time  bounded heuristic search. The central theme of my doctoral work will be that taking advantage of additional information can improve the performance of heuristic search algorithms.

Programming agent behaviors is a tedious task. In HITAB, agents learn a hierarchical finite state automata The difficulty increases in a multiagent setting due to the increased (HFA) represented as a Moore machine where individual size of the design space. Density of interactions, the states correspond to agent behaviors or another HFA. An number of agents and the agent's heterogeneity (both capabilities HFA is built iteratively: staring with a behavior library consisting and behaviors) all contribute to the larger design space. The now expanded One training approach is Learning from Demonstration behavior library is then used to train an even more (LfD) in which agents learn behaviors in real-time based on complex behavior which is then saved to the library, and provided examples from a human demonstrator.

A baby experiencing the world for the first time faces a considerable challenging sorting through what William James called the "blooming, buzzing confusion" of the senses. With the increasing capacity of modern sensors and the complexity of modern robot bodies, a robot in an unknown or unfamiliar body faces a similar and equally daunting challenge. Addressing this challenge directly by designing robot agents capable of resolving the confusion of sensory experience in an autonomous manner would substantially reduce the engineering required to program robots and the improve the robustness of resulting robot capabilities. Working towards a general solution to this problem, this work uses distinctive state abstractions and sensorimotor embedding to generate basic knowledge of sensor structure, local geometry, and object geometry starting with uninterpreted sensors and effectors.

The development of service robots has gained more and more attention over the last years. Advanced robots have to cope with many different situations and contingencies while executing concurrent and interruptable complex tasks. To manage the sheer variety of different execution variants the robot has to decide at run-time for the most appropriate behavior to execute. That requires task coordination mechanisms that provide the flexibility to adapt at run-time and allow to balance between alternatives.

For my thesis work I am developing a method for evaluating and standardizing ontologies based on an integration of the Basic Formal Ontology (BFO) and OntoClean. BFO serves as the upper ontology for the domain ontologies of the Open Biomedical Ontologies (OBO) Foundry. The OBO Foundry initiative is a collaborative effort for developing interoperable, science-based ontologies. OntoClean is an approach for the quality assurance of ontologies, and helps a modeler detect when the subsumption relation is used improperly. Ontologies developed for OBO use include some that have been ratified, and others holding the status of “candidate”. To maintain consistency between ontologies, it is important to establish formal principled criteria that a candidate ontology must meet for ratification. The formalisms that result from our integration will serve as criteria an OBO Foundry candidate ontology must satisfy in order to be ratified. The formalisms will also serve as a constraints within a prototype of an ontology editor that interactively asks a modeler questions that helps alleviate constraint violations.

Agent-based negotiation teams are negotiation parties formed by more than a single individual. Individuals unite as a single negotiation party because they share a common goal that is related to a negotiation with one or several opponents. My research goal is providing agent-based computational models for negotiation teams in multi-agent systems.

PODTGolog [Rens, 2010] is a Golog dialect attempting Broadly speaking, my research concerns combining to deal with partially observable MDP (POMDP) logic of action and POMDP theory in a coherent, environments. PODTGolog has not been given a mathematical theoretically sound language for agent programming.

In this proposal, we introduce Bayesian Abductive Logic Programs (BALP), a probabilistic logic that adapts Bayesian Logic Programs (BLPs) for abductive reasoning. Like BLPs, BALPs also combine first-order logic and Bayes nets. However, unlike BLPs, which use deduction to construct Bayes nets, BALPs employ logical abduction. As a result, BALPs are more suited for problems like plan/activity recognition that require abductive reasoning. In order to demonstrate the efficacy of BALPs, we apply it to two abductive reasoning tasks — plan recognition and natural language understanding.