Automated Planning: Workflow Allocation in a Mobile Setting

-        and its PDDL Domain Generator

PDDL2.1 domain generator:

We provide a generator to generate planning domains in PDDL2.1 and problem instances that can take user inputs to specify parameters.

 

The generator can be downloaded here, or as a single .zip package here.

 

There is a README file to help you. More background is provided below.

 

The problem is very difficult for most existing planners. For example, SGPlan can only solve very small instances.

To see a very simple example workflow problem and it's corresponding PDDL files click here.

Background:

Workflows are commonly used to coordinate the activities of various people to achieve some common goal. In its most basic form, a workflow is a set of tasks that must be completed in some order. Workflows are often modeled as directed acyclic graphs where the nodes represent tasks and the edges represent the ordering relation for the execution of the tasks. A simple example is shown below:

In this workflow, task A must be completed first. After task A is complete, tasks B and C can proceed in parallel but both must complete before task D can be executed.

Traditionally, workflows have been important in business contexts where business processes are described with workflows and the various workflow tasks are allocated to workers. This type of coordination is usually done with computers running workflow management software which can allocate the tasks to different users and communicate the results of completed tasks between users. With the advent of wireless computing devices, such as laptops and PDAs, people are able to work and communicate in a much more mobile setting. This raises many new potential applications for workflow.

One potentially interesting scenario for workflow in a mobile setting would be the creation of a workflow, ad hoc, to be administered to a group of workers in a large open area but where the workers may already be working on different tasks. For example, consider a group of construction workers moving around a large construction site like the one shown at the top of this page. All the workers are equipped with PDAs and are moving around the site working according to their individual schedules, which may be known to the management. Now imagine that the management wants to perform a safety inspection check ad hoc during the day and decides to request that a safety inspection report be compiled. The various steps in creating the report are shown as a workflow below:

The workflow allocation problem:

Notice that some of the tasks that make up the workflow can only be done in specific locations and may require certain qualifications in order to be performed. For example, only a structural engineer working near the scaffolding can perform the inspect scaffolding task. Because the workers already have strict schedules, the choice of worker for a given task is limited to the qualified workers that will be near where the task must be performed for enough time to perform the task. A further complication is that after a task is executed, the results will need to be communicated to the person(s) executing the subsequent task or tasks in the workflow. This transfer of results is normally done over a network but because the construction site is large, there may be no network infrastructure and we assume two people can only communicate when their mobile devices are within range of one another. This means that even if a worker can execute a task, we must consider whether or not the worker will be able to pass the result on to the person we have chosen to perform the subsequent task. All of these constraints can make the process of choosing a worker for a given task a non-trivial problem. In fact, deciding whether or not there is an allocation of tasks to workers such that the workflow could possibly complete in this manner is NP-hard.

To specify the problem more precisely, assume we are given a workflow which we can break into a set of tasks.

For each task we have:

 

We also have a set of workers which we will call hosts:

For each host we have:

The problem:

Determine if there is a feasible allocation. A feasible allocation is a mapping of tasks to hosts such that each host can execute all its assigned tasks. In order for a host to execute a task T, the host must have the qualifications required by T, be in the location for the duration specified by T, and must be able to receive the results from the host(s) executing the dependencies of T. Assume hosts can trade results whenever they are within a certain communication range of one another and furthermore, the results may be relayed through other hosts. Note that the requirement that a host receive results for all the dependencies before executing its task ensures that the workflow is completed in the order specified by the workflow′s ordering constraints.

Modeling as a planning problem:

To model this problem in terms of a planning language, we can define two kinds of actions; the execution of a task and the communication of a task′s result. We can let the planner explore the possible combinations of task execution actions and communication actions to reach the goal that all tasks in the workflow are executed. Any solution found would indicate a feasible alloaction and the task execution actions used in the solution would reveal the mapping of tasks to hosts.

In order to do this, we first determine which hosts can execute which tasks and during what time intervals. We call each window of time for a particular host to execute a particular task an execution opportunity. We can construct a list of all the execution opportunities for each task by examining the motion profile of each host that has the qualifications to execute the task.

We call a communication opportunity a window of time when two specific hosts are within a certain distance of each other. We can construct a list of communication opportunities for each pair of hosts by calculating the Euclidian distance between the hosts throughout the time intervals listed in their motion profiles.

Using the Planning Domain Definition Language, we can define every execution opportunity as an action that results in the corresponding task being completed. We can also define each communication opportunity between a pair of hosts as an action that results in any execution results on one host being duplicated onto the other. We will assign the goal for the problem to be that all the tasks are completed. This approach implies that a number of objects such as hosts be defined and we still need to define a number of preconditions and effects on the actions to enforce all the constraints of the workflow problem.

Thus in more detail:

We have the following objects:

 

Predicates:

Functions:

Actions - Execution Opportunities: As mentioned, each opportunity to execute a task by a specific host during a specific window of time is represented as an action.

Actions - Communication Opportunities: As mentioned, each opportunity to communicate between a pair of hosts during a window of time is represented as a separate action.

Goal: The FINISHED predicate associated with every task must be true for the global state object.




A simple example


To see a very simple example workflow problem and it's corresponding PDDL files click here.

 

 

Credits

 

The contributors to this project are Mart Haitjema, Yixin Chen, Catalin Roman, and Chris Gill.

 

Please contact Yixin Chen (chen at cse.wustl.edu) for any questions.

 

Please use this website as the reference to this work.