Abstract:
Decentralized resource allocation is a key problem for large-scale autonomic (or self-managing) computing systems. Motivated by a data center scenario, this paper explores efficient techniques for resolving resource conflicts via cooperative negotiation. Rather than computing in advance the functional dependence of each element’s utility upon the amount of resource it receives, which could be prohibitively expensive, each element’s utility is elicited incrementally. Such incremental utility elicitation strategies require the evaluation of only a small set of sampled utility function points, yet they find near-optimal allocations with respect to a minimax regret criterion. The paper describes preliminary computational experiments that illustrate the benefit of this approach.
Campbell, M., Joseph Hoane Jr., A. and Hsu, F., Deep Blue, Artificial Intelligence 134 (1-2), 2002.
Abstract:
This paper describes the Deep Blue system, the chess machine that defeated then-reigning World Chess Champion Garry Kasparov in 1997, and gives some of the rationale that went into the design decisions behind Deep Blue.
Guarino, Nicola and Chris Welty. 2002. Evaluating Ontological Decisions with OntoClean. Communications of the ACM. 45(2):61-65. New York:ACM Press.
Abstract:
This paper describes a methodology for evaluating an ontology using formal evaluation criteria. More specifically, it proposes a number of tests for identifying ill-defined subsumption relationships, and describes the formal basis for why they are wrong.
Kakade, S., Kearns, M. and Langford, J. Exploration in metric state spaces. ICML 2003.
Abstract:
This paper describes a provably near-optimal algorithm for reinforcement learning in Markov decision processes in which there is a natural metric on the state space that allows the construction of accurate local models.
Kothari, R. and Jain, V., Learning from Labeled and Unlabeled Data Using a Minimal Number of Queries, IEEE Transactions on Neural Networks, 2003.
Abstract:
This paper shows how to learn in situations where there is a very small amount of labeled data and a large amount of unlabeled data.
Mccarthy, J., Marvin, M., Sloman, A., Gong, L., Lau, T., Morgenstern, L., Mueller, E.T., Riecken, D., Singh, M. and Singh, P. An architecture of diversity for commonsense reasoning, IBM Systems Journal, vol. 41(3):530-39, 2002.
Abstract:
This paper discusses commonsense reasoning and what makes it difficult for computers. The paper contends that commonsense reasoning is too hard a problem to solve using any single artificial intelligence technique. A multilevel architecture is proposed that consists of diverse reasoning and representation techniques that collaborate and reflect in order to allow the best techniques to be used for the many situations that arise in commonsense reasoning. Story understanding--specifically, understanding and answering questions about progressively harder children's texts--is presented as a task for evaluating and scaling up a commonsense reasoning system.
Mueller, E.T. Story understanding through multi-representation model construction. In Graeme Hirst & Sergei Nirenburg (Eds.), Text Meaning: Proceedings of the HLT-NAACL 2003 Workshop (pp. 46-53). East Stroudsburg, PA: Association for Computational Linguistics.
Abstract:
In the last few years, a number of advances have occurred in the field of commonsense reasoning. First, formalisms have been developed for reasoning about action that are able to deal with the frame problem. Second, significant axiomatizations of commonsense knowledge have been developed using these formalisms. Third, efficient methods for performing commonsense reasoning using satisfiability (SAT) have been developed. This paper applies these advances to the problem of deep language understanding. A computer program is presented that contains multiple representations of commonsense knowledge, takes a narrative as input, transforms the narrative and representations of commonsense knowledge into a satisfiability problem, runs a satisfiability solver, and produces models of the narrative as output. The narrative, models, and representations are expressed in the language of Shanahan's event calculus.
Rish, I., Brodie, M, and Ma, S., Accuracy versus efficiency in probabilistic diagnosis, Proceedings of National Conference on Artificial Intelligence. 2002. p. 560-6, July 2002.
Abstract:
This paper studies the accuracy/efficiency trade-off in probabilistic diagnosis formulated as finding the most-likely explanation (MPE) in a Bayesian network. This work is motivated by a practical problem of efficient real-time fault diagnosis in computer networks using test transactions, or probes, sent through the network. The key efficiency issues include both the cost of probing (e.g., the number of probes), and the computational complexity of diagnosis, while the diagnostic accuracy is crucial for maintaining high levels of network performance. Herein, the paper derives a lower bound on the diagnostic accuracy that provides necessary conditions for the number of probes needed to achieve an asymptotically error-free diagnosis as the network size increases, given prior fault probabilities and a certain level of noise in probe outcomes. The paper also explores accuracy/efficiency trade-offs for very simple and efficient local approximation techniques, based on variable-elimination (the mini-bucket scheme).
Walsh, W.E., Das, R., Tesauro, G. and Kephart, J.O., Analyzing Complex Strategic Interactions in Multi-Agent Systems, Game Theory & Decision Theory Workshop, AAAI, 2002.
Abstract:
The paper develops a model for analyzing complex games with repeated interactions, for which a full game-theoretic analysis is intractable. This approach treats exogenously specified, heuristic strategies, rather than the atomic actions, as primitive, and computes a heuristic-payoff table specifying the expected payoffs of the joint heuristic strategy space. The paper analyzes two games based on (i) automated dynamic pricing and (ii) continuous double auction. For each game, the paper computes Nash equilibria of previously published heuristic strategies. To determine the most plausible equilibria, the replicator dynamics of a large population playing the strategies are studied. In order to account for errors in estimation of payoffs or improvements in strategies, the paper also analyzes the dynamics and equilibria based on perturbed payoffs.
Ye, Y. and Tu, Y. Dynamics of coalition formation in combinatorial markets. IJCAI 2003.
Abstract:
This paper studies the dynamics of agent mediated combinatorial trading at the macroscopic level. The combinatorial marketplace consists of a retailer who wishes to sell bundles of items, and a large number of agents with different purchasing goals. These agents dynamically form coalitions to exploit the benefits of grouping based on their complementary needs. a novel physics based dynamic equation is proposeed to capture the essence of the movements of agents among different sized coalitions. Simulation experiments are performed to study the global behavior of the agents and the effectiveness of the agent mediated combinatorial trading.