Time, chance and action

Peter HaddawyUAI 1990

TL;DR

This paper introduces a novel temporal probability logic designed to enable intelligent agents to reason about actions and their uncertain consequences over time. By integrating modal and probabilistic constructs, the logic can distinguish between possibility, probability, and truth, paving the way for more sophisticated planning in complex, real-world scenarios.

What Problem Does This Paper Address?

Intelligent agents operating in the real world need to make decisions based on their understanding of how their actions affect the environment. However, the real world is inherently uncertain. We rarely have complete information about the state of the world, and the outcomes of our actions are often probabilistic. Traditional logics for reasoning about actions, while useful, often struggle to capture this uncertainty and the temporal dynamics of events. For instance, stating "If I were to smoke, I would contract lung cancer some years down the road" is not a statement of certainty but of high likelihood, influenced by numerous unknown factors. This paper addresses the need for a formal framework that can represent and reason about actions, time, and uncertainty simultaneously, allowing agents to make more informed and robust decisions.

Methods

The core contribution of this paper is the development of a future-branching temporal probability logic. This logic is built upon a formal model of time that views it as a tree of possible world-histories, branching into the future. Key elements of the approach include:

  • Temporal Ontology: Time is modeled as a collection of world-histories, forming a tree structure where the past is determined, but the future is open. Facts hold over intervals, and events occur over intervals.
  • Modal and Probabilistic Constructs: The logic integrates modal operators (like $\Box$ for inevitability and $\Diamond$ for possibility) with a probabilistic operator ($P_t(\phi) \ge \alpha$) to express probabilities at specific times. This allows for nuanced statements about likelihood.
  • Distinguishing Truth, Possibility, and Probability: The logic explicitly differentiates between what is necessarily true, what is possibly true, and what is likely to be true, which is crucial for realistic reasoning.
  • Representation of Action Effects: The logic can represent how actions and other events affect future states probabilistically, including concurrent actions and conditions that change during an action's execution.
  • Probabilistic Causality: The framework supports reasoning about causal relationships, particularly through a condition that captures "positive influence" of one event on another, which implicitly handles temporal precedence and possibility.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Framework for Time, Chance, and Action: The most significant insight is the successful integration of temporal reasoning, probabilistic uncertainty, and action representation into a single logical framework. This is a crucial step towards building more intelligent agents.
  • Objective Probability: The paper focuses on objective probability, defined over possible futures, which is essential for reasoning about the inherent uncertainty of the world, as opposed to subjective beliefs.
  • Miller's Principle: The logic naturally supports Miller's principle, which states that the probability of a sentence at a given time is the expected value of its probability at any future time. This principle is vital for inferring current probabilities from future ones.
  • Distinguishing Potential vs. Actual Causation: The logic's ability to represent both probabilistic and deterministic outcomes allows for a clear distinction between potential causation (e.g., "smoking might cause cancer") and actual causation (e.g., "this specific action did cause this specific outcome").

Key Results

The paper presents the syntax and semantics of the temporal probability logic and provides several examples of how it can be used to represent complex scenarios. For instance, it demonstrates how to express:

  • The impossibility of concurrent actions (e.g., raising and lowering an arm simultaneously).
  • Probabilistic effects of actions influenced by conditions (e.g., a souffle's success depending on oven temperature).
  • Statements combining probability and inevitability (e.g., a 50% chance of an inevitable train crash).
  • Distinguishing between truth and unlikely events (e.g., winning the lottery despite low odds).

The paper also shows how the logic can be used to reason about the feasibility of plans, such as carrying two carry-on bags onto a plane, by calculating the probability of success given uncertain conditions like the plane being full.

Limitations and Future Work

  • Propositional Logic: The current logic is propositional. The authors acknowledge that adding quantification would significantly enhance its expressive power, allowing for more general statements about objects and their properties.
  • Action Attempts vs. Occurrences: The paper currently does not distinguish between an agent attempting an action and the action occurring. Future work will elaborate on this distinction to better model agent behavior.
  • Subjective Probability: The logic focuses on objective probability. Incorporating subjective probabilities (representing an agent's beliefs) is a key direction for future research, enabling agents to reason about their own knowledge and uncertainty. This would involve defining probability functions over all worlds, not just accessible ones, and introducing additional probability operators.
  • Axiomatization: The paper intentionally avoids providing complete axiomatizations, focusing instead on the logic's semantics and its utility as a tool for designing planning algorithms. The authors believe that specialized algorithms, rather than general theorem provers, are more appropriate for solving planning problems.

Summary updated

BibTeX
@inproceedings{haddawy1990time,
  author = {Peter Haddawy},
  title = {{Time, chance and action}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1990},
}
Figure