Mark S. Boddy

ICAPS Conference 2005 Conference Paper

Course of Action Generation for Cyber Security Using Classical Planning

• Mark S. Boddy
• Johnathan Gohde
• Thomas Haigh
• Steven A. Harp

We report on the results of applying classical planning techniques to the problem of analyzing computer network vulnerabilities. Specifically, we are concerned with the generation of Adversary Courses of Action, which are extended sequences of exploits leading from some initial state to an attacker’s goal. In this application, we have demonstrated the generation of attack plans for a simple but realistic web-based document control system, with excellent performance compared to the prevailing state of the art in this area. In addition to the new capabilities gained in the area of vulnerability analysis, this implementation provided some insights into performance and modeling issues for classical planning systems, both specifically with regard to Metric-FF and other forward heuristic planners, and more generally for classical planning. To facilitate additional work in this area, the domain model on which this work was done will be made freely available. See the paper’s Conclusion for details.

TIME Conference 1997 Conference Paper

Practical Temporal Reasoning for Real Scheduling Applications

• Mark S. Boddy

Summary form only given. Presents a set of requirements for modelling and solving scheduling problems, including a somewhat unconventional definition of the term "solution". These requirements, distilled from experience implementing and fielding scheduling systems in a wide variety of domains, strongly constrain the nature of a useful scheduling system. Using a set of example problems drawn from this experience, the author motivates and explicates an approach to temporal reasoning for scheduling in which the system dynamics encoded in the temporal representation are "convex", in the sense that all disjunction is treated as a range, rather than as a set of discrete points or regions of feasibility. Non-convex disjunction is encoded explicitly in a set of variables, such that finding a complete assignment to the set of variables is equivalent to constructing a feasible schedule. The problem is then solved as a Constraint Satisfaction Problem. Finally, the author discusses some recent extensions of this work, applying the same approach to problems involving a more complex system dynamic.

ICAPS Conference 1996 Conference Paper

Expressive Planning and Explicit Knowledge

• Robert P. Goldman
• Mark S. Boddy

We are concerned with the implications and interactions of three common expressive extensions to classical planning: conditional plans, context-dependent actions, and nondeterministic action outcomes. All of these extensions have appeared in recent work, sometimes in conjunction, but the semantics of the combination has not been fully explored. As we have argued in previous work, providing a coherent semantics for conditional planning with context-dependent actions requires that the planner’s information state be modeled separately from the world state. In this paper, we present a new planning language, WCPL, encompassing these extensions. The semantics of WCPL includes an explicit treatment of the planner’s information state as knowledge, as opposed to some form of context labelling. In addition to clarifying and unifying a disparate set of results from earlier work, we extend that work: WCPL handles both conditional and fail-safe plans for an action representation including both context-dependent and nondeterministic actions.

ICAPS Conference 1994 Conference Paper

Conditional Linear Planning

• Robert P. Goldman
• Mark S. Boddy

In this paper we present a sound and complete lln. ear planning algorithm which accomodatesconditional actions: actions whose effects cannot be predkted with certainty. Coaditioaal liaear planain8 is si~ificantly simpler than conditional non-linear plannin8 in conception and implementation. Furthermore, the eflldency tradeol which favor non-linear planning do not n~__~__rilycarry over with the same force to planning with conditional actions. Wehave applied our conditional linear planner, PLINTH, to the pmblent of planning imagepmc__*J~_’_ug actions for NASA’s Earth Observing System. Wediscuss the extension of PLm’mto probtbilktic planning.

UAI Conference 1994 Conference Paper

Epsilon-Safe Planning

• Robert P. Goldman
• Mark S. Boddy