The goal of this project is to develop powerful algorithms that can help computer programs make sophisticated decisions when faced with real-life problems. The project's novelty is its specific focus on automated reasoning where the relevant information is a combination of certain (deterministic) and uncertain (probabilistic) information. The need to accommodate both types of information is motivated by many real world problems such as scheduling of operating rooms and the diagnosing the nature of a disease, where situation assessment, planning or decision-making often involve taking into consideration both hard constraints and probabilistic information. A unique aspect of the project is that its algorithms will be founded upon a single theoretical framework--AND/OR search, developed by the investigator--which is driven by the graphical representation of the problems and often results in exponentially reduced complexities. The guiding principle behind the algorithms is the exploitation of useful structural features of a given problem instance, such as decomposability, sub-problem equivalence, and sub-problem irrelevance. The work proposed here promises to enhance problem-solving knowledge not just in the field of artificial intelligence, but also in the scientific community in general. As they are completed, the new algorithms will be posted on a publicly available Web site.
