Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Filters

2011 - 20132

Settings

Subject: search.filters.subject.Automated Planning

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Search Complexities for HTN Planning
    (2013) Alford, Ronald Wayne; Nau, Dana S; Kuter, Ugur; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Hierarchical Task Network (HTN) planning is the problem of decomposing an initial task into a sequence of executable steps. Often viewed as just a way to encode human knowledge to solve classical planning problems faster, HTN planning is more expressive than classical planning, even to the point of being undecidable in the general case. However, HTN planning is not just a way to solve planning problems faster, but is itself a search problem that can benefit from its own distinct search algorithms and heuristics. The dissertation examines the complexities of various HTN planning problem classes in order to motivate the development of heuristic search algorithms for HTN planning which are guaranteed to terminate on a large class of syntactically identifiable problems, as well as domain independent heuristics for those algorithms to use. This will allow HTN planning to be used in a number of areas where the solvability of a problem is in question, including during the initial development of a domain and for use in policy generation in non-deterministic planning environments. In particular, this dissertation analyzes two commonly used algorithms for HTN planning and describes the subsets of HTN problems that these algorithms terminate on. This allows us to discuss the run-times of these algorithms and com- pare the expressivity of the classes of problems they decide. We provide two new HTN algorithms which terminate on a strictly broader and more expressive set of HTN problems. We also analyze the complexity of delete-free HTN planning, an analogue to delete-free classical planning which is the base of many classical planning heuristics. We show that delete-free HTN planning is NP-complete, putting the existence of strict-semantics delete-relaxation-based HTN heuristics out of reach for practical purposes. Finally, we provide a translation of a large subset of HTN planning to classical planning, which allows us to use a classical planner as a surrogate for a heuristic HTN planner. Our experiments show that even small amounts and incomplete amounts of HTN knowledge, when translated into PDDL using our algorithm, can greatly improve a classical planner's performance.
  • Thumbnail Image
    Item
    Cyber-security Risk Assessment
    (2011) Panjwani, Susmit; Baecher, Gregory B; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Cyber-security domain is inherently dynamic. Not only does system configuration changes frequently (with new releases and patches), but also new attacks and vulnerabilities are regularly discovered. The threat in cyber-security is human, and hence intelligent in nature. The attacker adapts to the situation, target environment, and countermeasures. Attack actions are also driven by attacker's exploratory nature, thought process, motivation, strategy, and preferences. Current security risk assessment is driven by cyber-security expert's theories about this attacker behavior. The goal of this dissertation is to automatically generate the cyber-security risk scenarios by: * Capturing diverse and dispersed cyber-security knowledge * Assuming that there are unknowns in the cyber-security domain, and new knowledge is available frequently * Emulating the attacker's exploratory nature, thought process, motivation, strategy, preferences and his/her interaction with the target environment * Using the cyber-security expert's theories about attacker behavior The proposed framework is designed by using the unique cyber-security domain requirements identified in this dissertation and by overcoming the limitations of current risk scenario generation frameworks. The proposed framework automates the risk scenario generation by using the knowledge as it becomes available (or changes). It supports observing, encoding, validating, and calibrating cyber-security expert's theories. It can also be used for assisting the red-teaming process. The proposed framework generates ranked attack trees and encodes the attacker behavior theories. These can be used for prioritizing vulnerability remediation. The proposed framework is currently being extended for developing an automated threat response framework that can be used to analyze and recommend countermeasures. This framework contains behavior driven countermeasures that uses the attacker behavior theories to lead the attacker away from the system to be protected.