×
Poole, David

The independent choice logic for modelling multiple agents under uncertainty. (English) Zbl 0902.03017

Artif. Intell. 94, No. 1-2, 7-56 (1997).
Summary: Inspired by game theory representations, Bayesian networks, influence diagrams, structured Markov decision process models, logic programming, and work in dynamical systems, the independent choice logic (ICL) is a semantic framework that allows for independent choices (made by various agents, including nature) and a logic program that gives the consequence of choices. This representation can be used as a specification for agents that act in a world, make observations of that world and have memory, as well as a modelling tool for dynamic environments with uncertainty. The rules specify the consequences of an action, what can be sensed and the utility of outcomes. This paper presents a possible-worlds semantics for ICL, and shows how to embed influence diagrams, structured Markov decision processes, and both the strategic (normal) form and extensive (game-tree) form of games within the ICL. It is argued that the ICL provides a natural and concise representation for multi-agent decision-making under uncertainty that allows for the representation of structured probability tables, the dynamic construction of networks (through the use of logical variables) and a way to handle uncertainty and decisions in a logical representation.

Cited in 71 Documents

MSC:

03B80 Other applications of logic
91A05 2-person games
91A35 Decision theory for games
68T27 Logic in artificial intelligence
68N17 Logic programming

Keywords:

multi-agent decision-making under uncertainty; independent choice logic; logic program; consequence of choices; modelling tool for dynamic environments with uncertainty; consequences of an action; possible-worlds semantics; influence diagrams; structured Markov decision processes; games

Software:

GOLOG
PDF BibTeX XML Cite
\textit{D. Poole}, Artif. Intell. 94, No. 1--2, 7--56 (1997; Zbl 0902.03017)
Full Text: DOI

References:

[1] Albus, J. S., (Brains, Behavior and Robotics (1981), BYTE Publications: BYTE Publications Peterborough, NH)
[2] Apt, K. R.; Bezem, M., Acyclic programs, New Generation Comput., 9, 335-363 (1991) · Zbl 0744.68034
[3] Bacchus, F., (Representing and Reasoning with Uncertain Knowledge (1990), MIT Press: MIT Press Cambridge, MA)
[5] Boutilier, C.; Dearden, R.; Goldszmidt, M., Exploiting structure in policy construction, (Proceedings IJCAI-95. Proceedings IJCAI-95, Montreal, Que. (1995)), 1104-1111
[6] Boutilier, C.; Friedman, N., Nondeterministic actions and the frame problem, (Working Notes AAAI Spring Symposium 1995—Extending Theories of Actions: Formal Theory and Practical Applications (1995))
[7] Boutilier, C.; Friedman, N.; Goldszmidt, M.; Koller, D., Context-specific independence in Bayesian networks, (Horvitz, E.; Jensen, F., Proceedings 12th Conference on Uncertainty in Artificial Intelligence (UAI-96). Proceedings 12th Conference on Uncertainty in Artificial Intelligence (UAI-96), Portland, OR (1996)), 115-123
[8] Boutilier, C.; Poole, D., Computing optimal policies for partially observable decision processes using compact representations, (Proceedings AAAI-96. Proceedings AAAI-96, Portland, OR (1996)), 1168-1174
[9] Breese, J. S., Construction of belief and decision networks, Comput. Intell., 8, 624-647 (1992)
[10] Brooks, R. A., A robust layered control system for a mobile robot, IEEE J. Robotics Automation, 2, 14-23 (1986)
[11] Clark, K. L., Negation as failure, (Gallaire, H.; Minker, J., Logic and Databases (1978), Plenum Press: Plenum Press New York), 293-322
[12] Dean, T. L.; Kanazawa, K., A model for reasoning about persistence and causation, Comput. Intell., 5, 142-150 (1989)
[13] Dean, T. L.; Wellman, M. P., (Planning and Control (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
[14] Draper, D.; Hanks, S.; Weld, D. S., Probabilistic planning with information gathering and contingent execution, (Proceedings 2nd International Conference on AI Planning Systems. Proceedings 2nd International Conference on AI Planning Systems, Menlo Park, CA (1994)), 31-36
[15] Fagin, R. Y.; Halpern, J. Y.; Moses, Y.; Vardi, M. Y., (Reasoning about Knowledge (1994), MIT Press: MIT Press Cambridge, MA)
[16] Forbes, J.; Huang, T.; Kanazawa, K.; Russell, S., The BATmobile: towards a Bayesian automated taxi, (Proceedings IJCAI-95. Proceedings IJCAI-95, Montreal, Que. (1995)), 1878-1885
[17] Fudenberg, D.; Tirole, J., (Game Theory (1992), MIT Press: MIT Press Cambridge, MA)
[18] Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, (Kowalski, R.; Bowen, K., Proceedings 5th Logic Programming Symposium. Proceedings 5th Logic Programming Symposium, Cambridge, MA (1988)), 1070-1080
[19] Haddawy, P., Representing Plans under Uncertainty: A Logic of Time, Chance, and Action, (Lecture Notes in Artificial Intelligence, Vol. 770 (1994), Springer: Springer Berlin) · Zbl 0875.68777
[20] Halpern, J. Y., An analysis of first-order logics of probability, Artificial Intelligence, 46, 311-350 (1990) · Zbl 0723.03007
[21] Halpern, J. Y.; Turtle, M. R., Knowledge, probability and adversaries, J. ACM, 40, 917-962 (1993) · Zbl 0783.68120
[22] Howard, R. A., From influence to relevance to knowledge, (Oliver, R. M.; Smith, J. Q., Influence Diagrams, Belief Nets and Decision Analysis (1990), Wiley: Wiley New York), 3-23, Chapter 1
[23] Howard, R. A.; Matheson, J. E., Influence diagrams, (Howard, R. A.; Matheson, J., The Principles and Applications of Decision Analysis (1981), Strategic Decisions Group: Strategic Decisions Group CA), 720-762
[24] Kanazawa, K., A logic and time nets for probabilistic inference, (Proceedings AAAI-91. Proceedings AAAI-91, Anaheim, CA (1991)), 360-365
[25] Koller, D.; Megiddo, N., The complexity of two-person zero-sum games in extensive form, Games and Economic Behavior, 4, 528-552 (1992) · Zbl 0758.90084
[26] Koller, D.; Pfeffer, A. J., Generating and solving imperfect information games, (Proceedings IJCAI-95. Proceedings IJCAI-95, Montreal, Que. (1995)), 1185-1192
[27] Kowalski, R., Logic for Problem Solving, (Artificial Intelligence Series (1979), North-Holland: North-Holland New York) · Zbl 0426.68002
[28] Levesque, H. J.; Reiter, R.; Lespérance, Y.; Lin, F.; Scherl, R. B., GOLOG: a logic programming language for dynamic domains, Reasoning about Action and Change. Reasoning about Action and Change, J. Logic Programming (1996), Special Issue on
[29] Luenberger, D. G., (Introduction to Dynamic Systems: Theory, Models and Applications (1979), Wiley: Wiley New York) · Zbl 0458.93001
[30] McCarthy, J., Applications of circumscription to formalizing common-sense knowledge, Artificial Intelligence, 28, 89-116 (1986)
[31] McCarthy, J.; Hayes, P. J., Some philosophical problems from the standpoint of artificial intelligence, (Meltzer, B.; Michie, D., Machine Intelligence, Vol. 4 (1969), Edinburgh University Press: Edinburgh University Press Edinburgh), 463-502 · Zbl 0226.68044
[32] Myerson, R. B., (Game Theory: Analysis of Conflict (1991), Harvard University Press: Harvard University Press Cambridge, MA) · Zbl 0729.90092
[33] Nilsson, N. J., Logic and artificial intelligence, Artificial Intelligence, 47, 31-56 (1991)
[34] (Oliver, R. M.; Smith, J. Q., Series in Probability and Mathematical Statistics. Series in Probability and Mathematical Statistics, Influence Diagrams, Belief Nets and Decision Analysis (1990), Wiley: Wiley Chichester)
[35] Pearl, J., (Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
[36] Poole, D., Probabilistic Horn abduction and Bayesian networks, Artificial Intelligence, 64, 81-129 (1993) · Zbl 0792.68176
[38] Poole, D., Exploiting the rule structure for decision making within the independent choice logic, (Besnard, P.; Hanks, S., Proceedings 11th Conference on Uncertainty in Artificial Intelligence (UAI-95). Proceedings 11th Conference on Uncertainty in Artificial Intelligence (UAI-95), Montreal, Que. (1995)), 454-463
[39] Poole, D., Logic programming for robot control, (Proceedings IJCAI-95. Proceedings IJCAI-95, Montreal, Que. (1995)), 150-157
[40] Poole, D., A framework for decision-theoretic planning I: combining the situation calculus, conditional plans, probability and utility, (Horvitz, E.; Jensen, F., Proceedings 12th Conference on Uncertainty in Artificial Intelligence (UAI-96). Proceedings 12th Conference on Uncertainty in Artificial Intelligence (UAI-96), Portland, OR (1996)), 436-445
[42] Poole, D.; Mackworth, A. K.; Goebel, R. G., (Computational Intelligence: A Logical Approach (1997), Oxford University Press: Oxford University Press New York)
[43] Przymusinski, T. C., Three-valued nonmonotonic formalisms and semantics of logic programs, Artificial Intelligence, 49, 309-343 (1991) · Zbl 0741.03014
[44] Puterman, M. L., Markov decision processes, (Heyman, D. P.; Sobel, M. J., Handbooks in Operations Research and Manement Science, Vol. 2 (1990), North-Holland: North-Holland Amsterdam), 331-434, Chapter 8
[45] Reiter, R., The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression, (Lifschitz, V., Artificial Intelligence and the Mathematical Theory of Computation: Papers in Honor of John McCarthy (1991), Academic Press: Academic Press San Diego, CA), 359-380 · Zbl 0755.68124
[46] Rivest, R. L., Learning decision lists, Machine Learning, 2, 229-246 (1987)
[47] Rosenschein, S. J.; Kaelbling, L. P., A situated view of representation and control, Artificial Intelligence, 73, 149-173 (1995)
[48] Russell, S. J.; Subramanian, D., Provably bounded-optimal agents, J. Artif. Intell. Res., 2, 575-609 (1995) · Zbl 0900.68091
[50] Schubert, L. K., Monotonic solutions to the frame problem in the situation calculus: an efficient method for worlds with fully specified actions, (Kyburg, H. E.; Loui, R. P.; Carlson, G. N., Knowledge Representation and Defeasble Reasoning (1990), Kluwer Academic Press: Kluwer Academic Press Boston, MA), 23-67
[51] Shoham, Y., Agent-oriented programming, Artificial Intelligence, 60, 51-92 (1993)
[52] Smith, J. E.; Holtzman, S.; Matheson, J. E., Structuring conditional relationships in influence diagrams, Oper. Res., 41, 280-297 (1993)
[53] von Neumann, J.; Morgenstern, O., (Theory of Games and Economic Behavior (1953), Princeton University Press: Princeton University Press Princeton, NJ) · Zbl 0053.09303
[54] Zhang, L.; Qi, R.; Poole, D., A computational theory of decision networks, International J. Approximate Reasoning, 11, 83-158 (1994) · Zbl 0816.90005
[55] Zhang, Y., A foundation for the design and analysis of robotic systems and behaviours, (Ph.D. Thesis (1994), Department of Computer Science, University of British Columbia: Department of Computer Science, University of British Columbia Vancouver, BC)
[56] Zhang, Y.; Mackworth, A. K., Will the robot do the right thing?, (Proceedings 10th Biennial Conference of the Canadian Society for Computational Studies of Intelligence. Proceedings 10th Biennial Conference of the Canadian Society for Computational Studies of Intelligence, Banff, Alta. (1994)), 255-262
[57] Zhang, Y.; Mackworth, A. K., Constraint nets: a semantic model for hybrid dynamic systems, Theoret. Comput. Sci., 138, 211-239 (1995) · Zbl 0874.68205
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.