Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Computationally-Optimal Real-Resource Strategies for Independent, Uninterruptible Methods
David Einav, Michael Fehling
This paper focuses on managing the cost of deliberation before action. In many problems, the overall quality of the solution reflects costs incurred and resources consumed in deliberation as well as the cost and benefit of execution, when both the resource consumption in deliberation phase, and the costs in deliberation and execution are uncertain and may be described by probability distribution functions. A feasible (in terms of resource consumption) strategy that minimizes the expected total cost is termed computationally-optimal. For a situation with several independent, uninterruptible methods to solve the problem, we develop a pseudopolynomial-time algorithm to construct generate-and-test computationally optimal strategy. We show this strategy-construction problem to be NP-complete, and apply Bellman's Optimality Principle to solve it efficiently.
Keywords: null
Pages: 145-158
PS Link:
PDF Link: /papers/90/p145-einav.pdf
AUTHOR = "David Einav and Michael Fehling",
TITLE = "Computationally-Optimal Real-Resource Strategies for Independent, Uninterruptible Methods",
BOOKTITLE = "Uncertainty in Artificial Intelligence 6 Annual Conference on Uncertainty in Artificial Intelligence (UAI-90)",
PUBLISHER = "Elsevier Science",
ADDRESS = "Amsterdam, NL",
YEAR = "1990",
PAGES = "145--158"

hosted by DSL   •   site info   •   help