Inference in cognitive maps
Cognitive mapping is a qualitative decision modeling technique developed over twenty years ago by political scientists, which continues to see occasional use in social science and decision-aiding applications. In this paper, I show how cognitive maps can be viewed in the context of more recent formalisms for qualitative decision modeling, and how the latter provide a firm semantic foundation that can facilitate the development of more powerful inference procedures as well as extensions in expressiveness for models of this sort.
The economic approach to artificial intelligence (position paper)
To take an economic approach to anything typically invokes three premises. First, that the fundamental problem to be solved is one of resource allocation. Second, that it is useful to model behavior in terms of a rationality abstraction. And third, that it is essential to consider how authority and activity may be decentralized. All three of these premises are being increasingly adopted (explicitly or implicitly) in artificial intelligence, and growing numbers of AI researchers are working within the economic paradigm.
Path Planning under Time-Dependent Uncertainty
Standard algorithms for finding the shortest path in a graph require that the cost of a path be additive in edge costs, and typically assume that costs are deterministic. We consider the problem of uncertain edge costs, with potential probabilistic dependencies among the costs. Although these dependencies violate the standard dynamic-programming decomposition, we identify a weaker stochastic consistency condition that justifies a generalized dynamic-programming approach based on stochastic dominance. We present a revised path-planning algorithm and prove that it produces optimal paths under time-dependent uncertain costs. We test the algorithm by applying it to a model of stochastic bus networks, and present empirical performance results comparing it to some alternatives. Finally, we consider extensions of these concepts to a more general class of problems of heuristic search under uncertainty.
Accounting for Context in Plan Recognition, with Application to Traffic Monitoring
Typical approaches to plan recognition start from a representation of an agent's possible plans, and reason evidentially from observations of the agent's actions to assess the plausibility of the various candidates. A more expansive view of the task (consistent with some prior work) accounts for the context in which the plan was generated, the mental state and planning process of the agent, and consequences of the agent's actions in the world. We present a general Bayesian framework encompassing this view, and focus on how context can be exploited in plan recognition. We demonstrate the approach on a problem in traffic monitoring, where the objective is to induce the plan of the driver from observation of vehicle movements. Starting from a model of how the driver generates plans, we show how the highway context can appropriately influence the recognizer's interpretation of observed driver behavior.
A computational market model for distributed configuration design
This paper presents a precise market model for a well-defined class of distributed configuration design problems. Given a design problem, the model defines a computational economy to allocate basic resources to agents participating in the design. The result of running these “design economies” constitutes the market solution to the original problem. After defining the configuration design framework, I describe the mapping to computational economies and our results to date. For some simple examples, the system can produce good designs relatively quickly. However, analysis shows that the design economies are not guaranteed to find optimal designs, and we identify and discuss some of the major pitfalls. Despite known shortcomings and limited explorations thus far, the market model offers a useful conceptual viewpoint for analyzing distributed design problems.
Toward inquiry-based education through interacting software agents
The University of Michigan Digital Library (UMDL) project is creating an infrastructure for rendering library services over a digital network. When fully developed, the UMDL will provide a wealth of information sources and library services to students, researchers, and educators. Tasks are distributed among numerous specialized modules called agents. The three classes of agents are user interface agents, mediator agents, and collection interface agents. Complex tasks are accomplished by teams of specialized agents working together-for example, by interleaving various types of search. The UMDL is being deployed in three arenas: secondary-school science classrooms, the University of Michigan library, and space-science laboratories. The development team expects the scale and diversity of the project to test their technical ideas about distributed agents, interoperability, mediation, and economical resource allocation.
Toward a Market Model for Bayesian Inference
We present a methodology for representing probabilistic relationships in a general-equilibrium economic model. Specifically, we define a precise mapping from a Bayesian network with binary nodes to a market price system where consumers and producers trade in uncertain propositions. We demonstrate the correspondence between the equilibrium prices of goods in this economy and the probabilities represented by the Bayesian network. A computational market model such as this may provide a useful framework for investigations of belief aggregation, distributed probabilistic inference, resource allocation under uncertainty, and other problems of decentralized uncertainty.
Optimal Factory Scheduling using Stochastic Dominance A*
We examine a standard factory scheduling problem with stochastic processing and setup times, minimizing the expectation of the weighted number of tardy jobs. Because the costs of operators in the schedule are stochastic and sequence dependent, standard dynamic programming algorithms such as A* may fail to find the optimal schedule. The SDA* (Stochastic Dominance A*) algorithm remedies this difficulty by relaxing the pruning condition. We present an improved state-space search formulation for these problems and discuss the conditions under which stochastic scheduling problems can be solved optimally using SDA*. In empirical testing on randomly generated problems, we found that in 70%, the expected cost of the optimal stochastic solution is lower than that of the solution derived using a deterministic approximation, with comparable search effort.
Market-Oriented Programming: Some Early Lessons
As the other chapters in this volume attest, the market-based approach offers a useful way to conceptualize and analyze distributed control problems, as well as to design and implement actual distributed control systems. For the past few years, I have been exploring this approach not only as a methodology for solving particular distributed control problems, but also as a generic programming paradigm for the development of distributed systems based on these methods. By a programming paradigm, I mean that the exercise of defining a computational market leads to the specification of a procedural solution to the underlying allocation problem facing that market. I call this approach "market-oriented programming".
A market-based approach to allocating QoS for multimedia applications
Allocating quality of service (QoS) has been a focus of recent work on distributed multimedia systems and networks. This paper explores a decentralized approach that allocates QoS through a dynamic market. In our approach, each agent makes decisions according to its local knowledge and interests, and prices adjust to clear the market in each resource. Dynamic changes in agent needs and network status cause the agents to revise their decisions continually. The market prices reflect system-wide values, inducing agents to produce and consume appropriate amounts of the various resources. We describe a market model for allocating bandwidth in an actual networked meeting environment called FreeWalk. Experiments reveal the responsiveness of the market-based approach to dynamic conditions in allocating QoS for multimedia network applications.
