Exploiting the Rule Structure for Decision Making within the Independent Choice Logic

Author:

David Poole
Department of Computer Science,
University of British Columbia
2366 Main Mall
Vancouver, B.C., Canada V6T 1Z4
e-mail: poole@cs.ubc.ca
Phone: (604) 822-6254
FAX : (604) 822-5485

Abstract:

This paper introduces the independent choice logic, and in particular the ``single agent with nature'' instance of the independent choice logic, namely ICLdt. This is a logical framework for decision making uncertainty that extends both logic programming and stochastic models such as influence diagrams. This paper shows how the representation of a decision problem within the independent choice logic can be exploited to cut down the combinatorics of dynamic programming. One of the main problems with influence diagram evaluation techniques is the need to optimise a decision for all values of the `parents' of a decision variable. In this paper we show how the rule based nature of the ICLdt can be exploited so that we only make distinctions in the values of the information available for a decision that will make a difference to utility.

Keywords:

Independent Choice Logic, Influence Diagrams, Dynamic Programming, Logic Programs, Probabilistic Horn Abduction.

Availability:

To appear P. Besnard and S. Hanks (Eds.), Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers, San Mateo, 1995.

This paper is also available in postscript or gzipped postscript format.

Other information:

There are many related papers online (see my research overview).

The independent choice logic is an extension of Probabilistic Horn abduction to include a richer logic (including negation as failure), and choices by multiple agents. The most general overview is currently in:

D. Poole, "Sensing and Acting in the Independent Choice Logic" in Working Notes AAAI Spring Symposium on Extending Theories of Actions: Formal Theory and Practical Applications, Stanford, March, 1995. This paper overviews the Independent choice logic.

The following papers describe how the logic can be used for temporal reasoning.

D. Poole and K. Kanazawa, ``A decision-theoretic abductive basis for planning'', Proc. AAAI Spring Symposium on Decision-Theoretic Planning, Stanford University, March 1994. This paper shows how to use discrete time within the logic.

D. Poole, ``Logic Programming for Robot Control'', to appear Proc. 14th International Joint Conference on AI (IJCAI-95). This paper shows how to represent continuous time in the logic (probabilities are not emphasised).


uai@lis.pitt.edu / Last update: 24 May 1995