Automated Planning as a Semantic Technology

By   /  May 10, 2010  /  No Comments

This article describes the world of automated planning from the perspective of semantic technologies. It starts with background information on automated planning, where it can be applied, and its benefits. It also addresses some of the shortcomings of both planning and semantic technologies, and how both worlds can benefit from the experiences of the other. I also present challenges in integration of the two worlds, as well as an existing software planning system (HotPlanner) that is a result of such a successful integration.

What is automated, domain-independent planning

Automated, domain-independent planning is one of the core areas in Artificial Intelligence (AI), and active research in that area was conducted almost since the beginning of AI. While the performance of initial planning programs limited its application to toy-sized problems, the major breakthroughs in 1990s (GraphPlan) and at the beginning of the 21st century (FF planner) made automated planning applicable for real-life deployments. Automated planning can be applied to a variety of problems like configuration management, software system integration, project planning, controlling autonomous vehicles etc.

A planner is a program that is given the description of the current state of the world, description of available actions, and a set of goals that should be achieved. The program’s task is to create a plan; that is, to determine which actions have to be executed to achieve the goals, and what the constraints on the execution of actions should be (e.g., ordering constraints among actions). For example, in logistics, a planning program may be given information about packages, trucks, drivers, customers, and their locations (current state of the world). The available actions may include driving a truck from one location to another, picking and dropping off packages, or refueling trucks, and the goals may include delivering all the packages to the customers while respecting delivery deadlines and minimizing fuel consumption. Logistic companies use specialized software to help them in achieving that task. That kind of software (domain-dependent planners) has been tailored to solve this one specific kind of problem well, and it usually includes a specialized algorithm and data representation suited for the domain. A modification to the problem being solved (e.g., taking into account time-behind-the-wheel limits for truck drivers) may require time-consuming changes to the whole planning system, whereas switching to a slightly different domain (e.g., optimizing the order in which packages are loaded onto a truck) may require writing a new system entirely from scratch.

Domain-independent planning, on the other hand, assumes that a planner should be able to find solutions in any planning domain that can be described in a way the planner can understand. Depending on the expressivity of the domain description language and the flexibility of planning algorithm, the same planning program may be able to reason in situations ranging from just a simple modification to an original problem to an entirely different planning domain. This added flexibility is especially beneficial in real-life situations when the problem being solved changes (e.g., new constraints on the planning problem appear; e.g., when the law changes), or when the actual problem is not fully specified when the system is created (e.g., in a dynamically changing distributed computing environment, it is impossible to specify what services will be hosted there, and what their dependencies will be).

However, there is no such thing as free lunch; the added flexibility of domain-independent planning comes at a price. Typically, domain-independent planners are slower than the specialized planners. Additionally, domain-independent planners require detailed specification of the planning domain, which is not only time-consuming but it may involve taking into account tradeoffs between the quality of the produced solutions and planning time. That is why many planners up-to-date used relatively simple ways to represent planning domain (e.g., STRIPS formalism or PDDL language), which allow the planner to predict the cause and effect of every action or to guide search more effectively. For more complex knowledge representations that was not always possible. As the result, planning performance used to deteriorate rapidly with increasing complexity of the planning domain, and the search often started to resemble brute-force search (trying all possible combinations of actions), which could not be completed in a reasonable time.

Hierarchical planning

One solution to the performance problems in more complex domains is to include additional knowledge (e.g., expert knowledge) in the description of the world that can guide the planner’s search. This can be in the form of preparing a hierarchy of actions, starting with more complex actions at the top, which in turn consist of less complex actions. Therefore, it is possible to tell the planner explicitly that a complex action of "delivering a package" consist of three less complex phases: "picking up a package," "transporting the package," and actual "delivery" (instead of expecting the planner to figure it out by itself while being busy reasoning about other issues like fuel optimization and hours-behind-the-wheel). This simple idea is the cornerstone of Hierarchical Task Network (HTN) planning, and this relatively small help (preparing the hierarchy is not significantly more complex than preparing the basic domain itself) improves performance significantly. An added benefit of HTN planning is that it also allows to specify templates for desired kinds of solutions a planner should produce; for example, the use of HTN can force the planner to produce only plans to adhere to the company’s internal policies.

Semantic technologies in planning

Interestingly, despite of its AI origin, planning has rarely been integrated with semantic technologies like OWL, RDF, and SPARQL. This lack of integration is even more surprising given the fact that one of biggest challenges for planning solutions is preparing a formal model of the world that is both accurate, and does not entail excessive computational complexity. This is a perfect place for the use of semantic technologies, which were designed to accurately represent complex real-life data. Therefore, OWL statements can be used to describe the current start of the world, as well as the preconditions of actions (i.e., axioms that have to be satisfied for an action to be executed at a given point in time; for example, in order to pick up a package the driver, car and package have to be at the same location). Moreover, OWL2 designers included the computational complexity of various constructs into the standard, and divided it into various profiles (e.g., EL, RL, QL) — each of the profiles can be characterized by different computational properties with respect to the reasoning time. As the result, the time required to check whether the preconditions are satisfied in the current state of the world can be predictable based on the OWL profile used.

However, OWL ontologies are designed to represent static data. Representing changes in the world, actions, and continuous processes is still a work in progress in the semantic web community. This may pose a problem for planning, which has to represent actions in the domain representation (especially describing the axioms that change as the result of the action, and also identifying concepts and invariants that are preserved). At the same time, this is an area where the semantic web community can benefit from the experiences in the planning community, where this problem was researched for years. Additionally, planners have to reason about ontologies that frequently change, depending on which actions are selected (e.g., transporting a package from place A to B removes the axiom saying that the package is at place A, and inserts another one saying that the package is at place B). Many reasoners do not support incremental reasoning, which impacts performance negatively, or they support incremental reasoning only in the TBox, which is unlikely to change in most planning applications.

Combining the two worlds

As mentioned early, combining the two worlds (planning and semantic web) has great potential, as these two areas often complement each other in areas. Automated planning can on its own reduce costs (e.g., by allowing to react faster to changing conditions rather than requiring manual replanning), and minimize human errors (in fact automated planning software can also be used to verify human-generated plans). Teamed together with semantic technologies, it can gain easy access to heterogenous data sources, which are now available as RDF data with increasing frequency. However, the combination of the two worlds also presents some challenges. For example, the OWL reasoners are not always very efficient at incremental reasoning in the presence of changing instance data but some promising work exists.

As an attempt to further combine the two worlds, Clark & Parsia developed an HTN-based planner — HotPlanner — that uses a domain description language based on OWL-S, and uses an OWL2 reasoner (Pellet) for domain and state knowledge base management, reasoning, and query answering. The use of hierarchical actions and additional expert knowledge (e.g., in the form of custom heuristic functions) provides good performance while allowing to use expressive domain description language, as well as optimization of plan for complex, multiple objectives. The use of OWL-S allows to represent the changes between the states of the world, which are needed to describe the effects of actions. The benefits of successfully combining the world of automated domain-independent planning with semantic reasoning allowed HotPlanner to be used in the applications in the defense industry and in cloud computing startups.

You might also like...

GDPR Compliance: A Data Transformation Opportunity

Read More →