Envisionment-based scheduling using time interval petri networks: Representation, inference, and learning

Many Artificial Intelligence decision-making systems operate in cycles. A typical problem- solving cycle might consist of deliberation, scheduling, and execution steps. At the deliberation step a number of feasible actions are generated. They are then evaluated by a scheduler at the scheduling step and the most suitable action is performed at the execution step.; A wide class of schedulers are based on the idea of modeling the environment to envision the effects of the action in question. This thesis presents a novel scheduling approach that compiles the relevant knowledge about the environment into the mathematically well-founded framework of Petri Nets. The Petri Net based environment model is then used to envision the effects of an action being evaluated. The action with most desirable envisioned effects is carried out at the execution step.; This interdisciplinary research has made the following five main contributions: (1) A Petri Nets based approach to decision-making scheduling through environment modeling is presented. Petri Nets formalism is known for its solid theoretical base, clear syntax and semantics, intuitive graphic representation, and native concurrency support. (2) The classical Petri Net model is extended in various ways to make it suitable for AI scheduling tasks. The main extensions concern explicit temporal reasoning, context, and operator support. The new formalism is hence called Time Interval Petri Nets (TIPNs). (3) TIPN properties and relation to other Al and Petri Nets formalisms are studied. We also present analysis methods facilitating verification and refinement of Petri Net models. (4) Two machine learning algorithms are developed to synthesize Petri Net models automatically or semi-automatically. One learning algorithm exploits the connection between Petri Nets and Horn clauses by using inductive logic programming methods (ILP) to learn Horn-clauses first and then convert them to TIPNs. The other algorithm employs a general-to-specific search in the space of Petri Net topologies starting with a given initial topology. (5) The framework is applied in the real-time decision-making domain of ship damage control for the tasks of automated problem-solving and intelligent tutoring (advising, critiquing, and scoring). In a large exercise involving approximately 500 simulated ship crisis scenarios, our decision-making expert system showed a 318% improvement over Navy officers by saving 89 more ships.