At birth, the human infant has only a very rudimentary perceptual system and similarly rudimentary control over its musculature. As time goes on, a child develops. Its ability to control, perceive, and predict its own behavior improves as it interacts with its environment. We are interested in the process of development, in particular with respect to activity. How might an intelligent agent of our own design learn to represent and organize procedural knowledge so that over time it becomes more competent at its achieving goals in its own environment? In this dissertation, we present a system that allows an agent to learn models of activity and its environment and then use those models to create units of behavior of increasing sophistication for the purpose of achieving its own internally-generated goals.

Sophisticated agents operating in open environments must make complex real-time control decisions on scheduling and coordination of domain activities. These decisions are made in the context of limited resources and uncertainty about the outcomes of activities. Many efficient architectures and algorithms that support these computation-intensive activities have been developed and studied. However, none of these architectures explicitly reason about the consumption of time and other resources by these activities, which may degrade an agent's performance. The problem of sequencing execution and computational activities without consuming too many resources in the process, is the meta-level control problem for a resource-bounded rational agent. The focus of this research is to provide effective allocation of computation and unproved performance of individual agents in a cooperative multi-agent system. This is done by approximating the ideal solution to meta-level decisions made by these agents using reinforcement learning methods. A meta-level agent control architecture for meta-level reasoning with bounded computational overhead is described. This architecture supports decisions on when to accept, delay or reject a new task, when it is appropriate to negotiate with another agent, whether to renegotiate when a negotiation task fails, how much effort to put into scheduling when reasoning about a new task and whether to reschedule when actual execution performance deviates from expected performance. The major contributions of this work are: a resource-bounded framework that supports detailed reasoning about scheduling and coordination costs; an abstract representation of the agent state which is used by hand-generated heuristic strategies to make meta-level control decisions; and a reinforcement learning based approach which automatically learns efficient meta-level control policies.

Design-to-time real-time scheduling is an approach to solving time-sensitive problems where multiple solution methods are available for many subproblems. The design-to-time approach involves designing a solution plan (i.e., an ordered schedule of solution methods) dynamically at runtime such that the solution plan uses the time available as productively as possible to try to maximize solution quality. The problem to be solved is modeled as a set of interrelated computational tasks, with alternative ways of accomplishing the overall task. There is not a single "right" answer, but a range of possible solution plans of different qualities, where the overall quality of a problem solution is a function of the quality of individual subtasks. The act of scheduling such pre-specified task structures that contain alternatives requires both deciding "what" to do and deciding "when" to do it. One major focus of our design-to-time work is on taking interactions among subproblems into account when building solution plans, both "hard" interactions that must be satisfied to find correct solutions (e.g., hard precedence constraints), and "soft" interactions that can improve (or hinder) performance. Another recent focus of our work has been on adding to the problem model the notion of uncertainty in the duration and quality of methods, and in the presence and power of soft interactions. Scheduling with uncertain information requires additions to the scheduling algorithm and the monitoring of method performance to allow dynamic reaction to unexpected situations.

The ability to create and to use abstractions in complex environments, that is, to systematically ignore irrelevant details, is a key reason that humans are effective problem solvers. Although the utility of abstraction is commonly accepted, there has been relatively little research on autonomously discovering or creating useful abstractions. A system that can create new abstractions autonomously can learn and plan in situations that its original designer was not able to anticipate. This dissertation introduces two related methods that allow an agent to autonomously discover and create temporal abstractions from its accumulated experience with its environment. A temporal abstraction is an encapsulation of a complex set of actions into a single higher-level action that allows an agent to learn and plan while ignoring details that appear at finer levels of temporal resolution. The main idea of both methods is to search for patterns that occur frequently within an agent's accumulated successful experience and that do not occur in unsuccessful experiences. These patterns are used to create the new temporal abstractions. The two types of temporal abstractions that our methods create are (1) subgoals and closed-loop policies for achieving them, and (2) open-loop policies, or action sequences, that are useful “macros.” We demonstrate the utility of both types of temporal abstractions in several simulated tasks, including two simulated mobile robot tasks. We use these tasks to demonstrate that the autonomously created temporal abstractions can both facilitate the learning of an agent within a task and can enable effective knowledge transfer to related tasks. As a larger task, we focus on the difficult problem of scheduling the assembly instructions for computers with multiple pipelines in such a manner that the reordered instructions will execute as quickly as possible. We demonstrate that the autonomously discovered action sequences can significantly improve performance of the scheduler and can enable effective knowledge transfer across similar processors. Both methods can extract the temporal abstractions from collections of behavioral trajectories generated by different processes. In particular, we demonstrate that the methods can be effective when applied to collections generated by reinforcement learning agents, heuristic searchers, and human tele-operators.

In the many successful applications of artificial intelligence (AI) methods to real-world problems in domains such as medicine, commerce, and manufacturing, the AI system usually plays an advisory or monitoring role. That is, the AI system provides information to a human decision-maker, who has the final say. However, for applications ranging from space exploration, to e-commerce, to search and rescue missions, there is an increasing need and desire for AI systems that display a much greater degree of autonomy. In designing autonomous AI systems, or agents, issues concerning safety, reliability, and robustness become critical. Does the agent observe appropriate safety constraints? Can we provide performance or goal-achievement guarantees? Does the agent deliberate and/or learn efficiently and in real time? In this dissertation, we address some of these issues by developing an approach to agent design that integrates control-theoretic techniques, primarily methods based on Lyapunov functions, with planning and learning techniques from AI. Our main approach is to use control-theoretic domain knowledge to formulate, or restrict, the ways in which the agent can interact with its environment. This approach allows one to construct agents that enjoy provable safety and performance guarantees, and that reason and act in real-time or anytime fashion. Because the guarantees are established based on restrictions on the agent's behavior, specialized “safety-oriented” decision-making algorithms are not necessary. Agents can reason using standard AI algorithms; we discuss state-space search and reinforcement learning agents in detail. To a limited degree, we also show that the control-theoretic domain knowledge needed to ensure safe agent behavior can itself be learned by the agent, and need not be known a priori. We demonstrate our theory with simulation experiments on standard problems from robotics and control.

An autonomous decision maker, such as an intelligent agent, must make decisions in the presence of uncertainty. Furthermore, in a multi-agent system where the agents are distributed, agents need to deal with not only uncertain outcomes of local events but also uncertainty associated with events happening in other agents in order to maintain proper coordination of the activities of the agents. This dissertation focuses on the problem of handling uncertainty and snaking decisions related to agent coordination in cooperative multi-agent systems. Our hypothesis is that the choice of coordination strategies must take into account the specific characteristics of the environments in which the agents operate in order to improve performance. Our goal is to provide a quantitative model and a set of tools and methodologies that can be used in evaluating and developing situation specific coordination strategies, to model uncertainty in coordination, and to facilitate understanding which information is necessary when making coordination decisions. Our approach is first to examine the types of uncertainty that need to be considered when making coordination decisions, and then to incorporate them explicitly in the decision making. The result is a richer semantics of agent commitments that quantitatively represent the possible effects of uncertain events, and we demonstrate its performance through simulation with a heuristic scheduler. We then move away from heuristic problem solving and establish a formal decision-theoretic framework for multi-agent decision making. We call this framework decentralized multi-agent Markov decision processes . It categorizes agent decisions into action decisions and communication decisions, and we experiment with communication decisions to demonstrate how the performance of different coordination strategies varies according to the environment parameters. Finally, to address the problem of complexity in solving the decision processes we have defined, and to provide a connection between centralized policies and decentralized policies, we develop a methodology for generating a set of decentralized multi-agent policies based on solving the centralized multi-agent Markov decision process. We study its performance by comparing it to heuristic policies and show how to reduce communication costs.

An outstanding problem in model-based recognition of objects by robot systems is how the system should proceed when the acquired data are insufficient to identify the model instance and model pose that best interpret the object. Such a situation can arise when there are multiple model instances that could be interpretations of the object, or when there are ambiguous poses of a given model instance. This work proposes a generic method for automatically finding a path along which the robot could move a tactile sensor, so that the robot system can uniquely and efficiently identify the object. The problem framework is defined, a methodology for finding paths is proposed, and an evaluation of the costs and benefits of sensing paths is presented, all of which must be done in the presence of geometric uncertainty about the possible locations and orientations of the object. The two-dimensional problem is solved by a projection-space approach, in which the optimal sensing path is found by efficiently searching through the sets of paths passing through each object face. A path is sought which distinguishes as many distinct interpretations as possible, subject to design constraints. It is shown that employing realistic assumptions the problem is tractable, and that for the two-dimensional case the solution time is comparable to the robot motion time. For the three-dimensional problem, an analysis of the structure of the path parameter space shows why the problem is inherently difficult. Several alternative solutions are examined, and a taxonomy of approaches classifies related work into a more general hierarchy of problem decompositions.

Knowledge-Based Systems (KBSs) that operate in the real-world must reason about their actions from information that is inherently uncertain, imprecise, and occasionally incorrect. Consequently, control-related information can be viewed as imperfect evidence that can potentially support or refute hypotheses about which actions are the most appropriate to pursue. Moreover, previous research has not thoroughly exploited the fact that knowledge about the degree to which evidence is certain, precise, and correct can significantly influence the choice of any alternative. It follows that the ability to make effective decisions is critically dependent upon the underlying technologies and knowledge that is brought to bear upon the task of choosing a course of action on the basis of evidential information. This dissertation, therefore, is concerned with the problem of developing an automated approach to reasoning about control that is well suited for real-world situations. The Dempster-Shafer (DS) theory of evidence is the mathematical foundation of an evidential reasoning (ER) technology upon which our proposed approach is based. Control-related evidence is derived from evidential measures such as ignorance, ambiguity, and dissonance that reflect the certainty, precision, and accuracy of domain knowledge and hypotheses of interest. These and other measures were also used to help characterize and reason about the current state and problem solving capabilities of a KBS. Dempster's rule is used to form a consensus opinion about the truth of hypotheses that the evidence directly impacts. An inference engine is used to infer the truth and falsity of the remaining dependent hypotheses, thus, inference-based control is a core paradigm in our approach. Evidential decision measures such as decisiveness were developed to help choose an action based upon the results of the inference process. A high-level computer vision KBS called OCULUS was built as a testbed for conducting a large number of control experiments. The results demonstrate that an evidential approach to control can significantly improve the system's ability to correctly interpret images by as much as 30%, and in most cases with less than a 10% increase in effort. They also suggest that the domain independent control strategies that were developed and used by the system can be very effective in other real-world task domains.

ADVISOR is a machine learning architecture for constructing intelligent tutoring systems (ITS). ADVISOR is able to automate some of the reasoning about how the student will probably perform, and all of the reasoning about which teaching action should be made in a particular context. The benefit of this approach is that it works by observing students using an ITS. By observing students, ADVISOR constructs a model of how a student will respond to a particular teaching action in a given situation. With this model, ADVISOR is able to experiment and determine a policy for presenting teaching actions that tries to achieve a customizable teaching goal. We experimented with a variety of approaches for constructing a model of how students behave, and we found that sophisticated approaches such as Multiple Adaptive Regression Splines (MARS) are only slightly better than linear regression. We also examined a variety of ways ADVISOR can reason with the model of student performance and determine how to teach. We used including temporal difference learning, heuristic search, and the use of rollouts. If little is known a prior about the teaching goal, rollouts are a strong choice as they require little prior knowledge and are robust. Given prior knowledge of the teaching goal, some type of temporal difference learning is a good option since this requires less computation time than using heuristic search or rollouts. ADVISOR was tested in the context of the AnimalWatch tutor for grade school arithmetic. However, the architecture is generic and applicable to a variety of ITS. As part of AnimalWatch, ADVISOR was tested in a grade school and achieved the specified teaching goal of minimizing the amount of time per problem. The ADVISOR architecture is also useful for evaluating what components of the tutoring system are responsible for performance, and what components of ADVISOR are constraining performance. In this way, engineering effort can be directed to where it is most profitable. Thus, the ADVISOR architecture has the potential to benefit a wide range of ITS (and possibly other adaptive systems) in several ways. In addition to determining which components limit performance, our hope is ADVISOR's ability to automate the construction of the knowledge of how to teach will result in a decreased cost to construct ITS.

While formal, decision-theoretic models such as the Markov Decision Process (MDP) have greatly advanced the field of single-agent control, application of similar ideas to multi-agent domains has proven problematic. The advantages of such an approach over traditional heuristic and experimental models of multi-agent systems include a more accurate representation of the underlying problem, a more easily defined notion of optimality and the potential for significantly better solutions. The difficulty often comes from the tradeoff between the expressiveness of the model and the complexity of finding an optimal solution. Much of the research in this area has focused on the extremes of this tradeoff. At one extreme are models where each agent has a global view of the world, and solving these problems is no harder than solving single-agent problems. At the other extreme lie very general, decentralized models, which are also nearly impossible to solve optimally. The work proposed here explores the middle-ground by starting with a general decentralized Markov decision process and introducing structure that can be exploited to reduce the complexity. I present two decision-theoretic models that structure the interactions between agents in two different ways. In the first model the agents are independent except for an extra reward signal that depends on each of the agents' histories. In the second model the agents have independent rewards but there is a structured interaction between their transition probabilities. Both of these models can be optimally and approximately solved using my Coverage Set Algorithm. I also extend the first model by allowing the agents to communicate and I introduce an algorithm that finds an optimal joint communication policy for a fixed joint domain-level policy.