loui@wucs1.wustl.edu (Ron Loui) (11/28/88)
note: please tell me if you think talk abstracts do not belong in this newsgroup. one used to see them more often, and in some cases the speaker's dept. requests the announcement. --r.p.loui COMPUTER SCIENCE COLLOQUIUM Washington University St. Louis 2 December 1988 Planning and Plan Execution Mark Drummond NASA Ames We are given a table on which to place three blocks (A, B, and C). We begin in a state where all the blocks are available for placement; there is also an unspecified means of transporting each block to its target location on the table. We might imagine that there are an unlimited number of interaction-free robot arms, or that each block may be levitated into place once it is available. The exact means for moving the blocks does not matter: given that a block is available it may be placed. The only constraint is that B cannot be placed last. We call this the "B-not-last" problem. We must produce a plan which is as flexible as possible. If a block can be placed then our plan must so instruct the agent. If a block cannot be placed according to the constraints then our plan must prevent the agent from attempting to place the block. The agent must never lock up in a state from which no progress is possible. This would happen, for instance, if A were on the table, and C arrived and was placed. B could then not be placed last. It takes four totally ordered plans or three partially ordered plans to deal with the B-not-last problem. In either representation there is no one plan that can be given to the assembly agent which does not overly commit to a specific assembly strategy. Disjunction is not the only problem. Actions will often fail to live up to the planner's expectations. An approach based on relevancy analysis is needed, where actions are given in terms of the conditions under which their performance is appropriate. The problem is even harder when there can be parallel actions. Our approach uses a modified Condition/Event system (Drummond, 1986a,b) as a causal theory of the application domain. The C/E system is amenable to direct execution by an agent, and can be viewed as a nondeterministic control program. For every choice point in the projection, we synthesize a "situated control rule" that characterizes the conditions under which action execution is appropriate. This can be viewed as a generalization of STRIPS' algorithm for building triangle tables from plan sequences (Nilsson, 1984). ________________________________________________________________________________ 5 December 1988 Coping with Computational Complexity in Medical Diagnostic Systems Gregory Cooper Stanford University/Knowledge Systems Laboratory Probabilistic networks will be introduced as a representation for medical diagnostic knowledge. The computational complexity of using general probabilistic networks for diagnosis will be shown to be NP-hard. Diagnosis using several important subclasses of these networks will be shown to be NP-hard as well. We then will focus on some of the approximation methods under development for performing diagnostic inference. In particular, we will discuss algorithms being developed for performing diagnostic inference using a probabilistic version of the INTERNIST/QMR knowledge base. -------------------------------------------------------------------------------- Computation and Inference Under Scarce Resources Eric Horvitz Stanford University Knowledge Systems Laboratory I will describe research on Protos, a project focused on reasoning and representation under resource constraints. The work has centered on building a model of computational rationality through the development of flexible approximation methods and the application of reflective decision-theoretic control of reasoning. The techniques developed can be important for providing effective computation in high-stakes and complex domains such as medical decision making. First, work will be described on the decision-theoretic control of problem solving for solving classical computational tasks under varying, uncertain, and scarce resources. After, I will focus on decision-theoretic reasoning under resource constraints. I will present work on the characterization of partial results generated by alternative approximation methods. The expected value of computation will be introduced and applied to the selection and control of probabilistic inference. Plans for extending the work to inference in a large internal-medicine knowledge base will be described. Finally, I extend the techniques beyond the tradeoff between computation time and quality of computational results to explore issues surrounding complex reasoning under cognitive constraints. ________________________________________________________________________________