Dynamic and Distributed Allocation of Resource

Constrained Project Tasks to Robots

Sanem Sariel

and Tucker Balch

Istanbul Technical University, Computer Engineering Dept., Istanbul TURKEY

Georgia Institute of Technology, College of Computing, Atlanta, GA, USA

Abstract. In this work, we propose a dynamic task selection scheme for allocat-

ing real-world tasks to the members of a multi-robot team. Tasks in our research

are subject to precedence constraints and simultaneous execution requirements.

This problem is similar to the Resource Constrained Project Scheduling Problem

(RCPSP) in operations research. Particularly, we also deal with the missions that

may change their forms by introducing new online tasks during execution making

the problem more challenging besides the real world dynamism. Unpredictabil-

ity of the exact processing times of tasks, unstable cost values during runtime

and inconsistencies due to uncertain information form the main difﬁculties of

the task allocation problem for robot systems. Since the processing times of the

tasks are not exactly known in advance, we propose a dynamic task selection

scheme for the eligible tasks instead of scheduling all of them to eliminate the

redundant calculations. In our approach, globally efﬁcient solutions are attained

by the mechanisms for forming priority based rough schedules by tentative coali-

tion commitments and selecting the most suitable tasks from these schedules. The

approach is distributed and computationally efﬁcient.

1 Introduction

In this work, we propose the Dynamic Priority-based Task Selection Scheme (DPTSS)

embedded in our framework, Distributed and Efﬁcient Multi Robot - Cooperation

Framework (DEMiR-CF), for allocating complex tasks with precedence constraints

and simultaneous execution requirements by a multi robot team. Robustness is pro-

vided through the integrated Plan B Precaution Routines [1]. DEMiR-CF is evaluated

in three different domains, [2], [3], [4]. In this article, we present the formal details of

our task allocation approach and the simulation scenarios on the US NAVY’s simulator

for dynamic tasks and events.

M+ [5] is one of the earlier cooperation schemes addressing many real time issues

including plan merging paradigms. One of the latest works, Zlot’s [6] task-tree auc-

tion method combined with the combinatorial auction based task allocation scheme,

TraderBots [7], is suitable for the complex tasks represented as and/or trees. Lemarie

et al. proposes a task allocation scheme for multi-UAV cooperation by balancing work-

loads [8]. Gancet [9] proposes a coordination framework addressing the planning and

allocation issues. These systems use the auction based task allocation approach which

Sariel S. and Balch T. (2006).

Dynamic and Distributed Allocation of Resource Constrained Project Tasks to Robots.

In Proceedings of the 2nd International Workshop on Multi-Agent Robotic Systems, pages 34-43

DOI: 10.5220/0001225100340043

 SciTePress

is scalable and robust. However as Dias et al. report, still there are not certain proce-

dures for re-planning, changing decomposition of tasks, rescheduling during execution

[10]. Our main objective is to design the certain components in an integrated cooper-

ation framework to deal with these issues and make it usable for as many domains as

possible.

We formulate the general multi-robot multi task allocation problem as a Resource

Constrained Project Scheduling Problem (RCPSP) [11]. Unpredictability of the exact

processing times of tasks, the unstable cost values during runtime and the inconsisten-

cies due to the uncertain information form the main difﬁculties of the task allocation

problem for the robot systems. To cope with these issues, we propose a dynamic task

selection scheme for the eligible tasks instead of scheduling all of them to eliminate

the redundant efforts. Particularly, we also deal with the real-world missions that may

change their forms by introducing new online tasks during the execution which makes

the problem more challenging besides the real world dynamism. Our generic task rep-

resentation is suitable for multi-robot teams and relaxes many assumptions for the real

world tasks. DPTSS provides a way to ﬁnd a solution to the problem from a global

perspective by the mechanisms for forming priority based rough schedules and select-

ing the most suitable tasks from these schedules. Rough schedules are formed by the

tentative coalition commitments which are agreed upon by the robots for the tasks with

simultaneous execution requirements. Therefore since the allocations are not made from

scratch, the scheduling costs are reduced and the communication requirements are kept

at minimum as much as possible.

2 Problem Statement

We formulate the multi-robot task allocation problem for complex missions as a ver-

sion of the well known NP-Hard Resource Constrained Project Scheduling Problem

(RCPSP) in operations research [11]. The adapted version of the formulation for our

multi robot task allocation problem on project tasks is given as follows. A complex

mission consists of a set of tasks T = {t

, ..., t

} which have to be performed by a

team of robots R = {r

, ..., r

}. The tasks are interrelated by two type of constraints.

First, the precedence constraints are deﬁned between activities. These are given by the

relations t

≺ t

, meaning that the task t

cannot start before the task t

is completed.

Second, a task t

requires a certain set of capabilities reqcap

and certain number of ro-

bots (resources) reqno

to be performed. We relax the limitation on reqno

by allowing

its change during the task execution based on the requirements which provides a more

realistic way of representing the real-world tasks. Therefore different alternative solu-

tions may be found to allocate the tasks to the robots based on the environmental factors.

Based on the given notation, the Scheduling Problem (ScP ) is deﬁned as determining

starting times of all the tasks in such a way that: the total reqno

for each task t

is less

than or equal to the number of available robots (R

= ∪r

) with reqcap

⊆ cap

(Condition-1, C1). The given precedence conditions (Condition-2, C2) are fulﬁlled ,

and the makespan C

max

= max(C

), 1 ≤ i ≤ n (Objective, O) is minimized, where

= S

+ p

is assumed to be the completion of task t

, where S

is the actual starting

time and p

is the actual processing time respectively. It’s not always possible to expect

the exact processing times (p) of the tasks of real world missions in which robots in-

volve. However to form a complete schedule, it is necessary to make an approximation

in terms of the best knowledge available. Since the schedules are subject to change,

we propose a way to allocate the tasks incrementally to the robots without ignoring the

overall global solution quality instead of scheduling all the tasks. Therefore the main

objective becomes determining which robot should do in a precedence and resource

feasible manner whenever a new task needs to be assigned, instead of scheduling all

the tasks from scratch. Although it is not a concern during the assignments are made,

preemption (i.e. yielding) is possible to maintain the solution quality and to handle the

failures during the execution. The main problem that we try to solve is given as follows:

The Selection Problem (SlP ) is determining the next action to select (either being idle

or executing a task) for each robot in such a way that the C1 and the C2 are fulﬁlled

and the O is minimized.

Missions can be represented by directed acyclic graphs (DAG) where each node

represents a task (with requirements) and the directed arcs (conjunctive arcs) represent

the precedence constraints among them. A sample graph for a small size mission for

moving the boxes to a stamping machine and dropping them in a given order, then

cleaning the room is given in Figure 1. Before dropping boxes into the mailbox, they

should ﬁrst be moved to the stamping machine. The room can only be cleaned after both

boxes are moved. Since the box 1 is heavy, two robots (reqno) are needed to move and

drop the box. Although this graph shows the relationships on the dependencies among

tasks, it does not show which robot performs which task in sequence.

The following deﬁnitions are needed for our formulation to the solution. Intuitively,

robots do not deal with the ineligible tasks (T

) as a union of tasks that are already

achieved or that are not eligible from the capabilities perspective. The eligible tasks

= T \ T

) for the robot r

consists of only the considerable tasks that are neither

in execution (T

) nor achieved. P

is deﬁned as the set of all predecessor tasks of the

task t

. We deﬁne an active task set as:

= {{t

} | reqcap

⊆ cap

, P

is completed, 0 < i ≤ n}, (T

⊆ T

), whereas

an inactive task set T

= T

contains the tasks for which the robot r

, reqcap

⊆

cap

, but the precedence constraints are not satisﬁed yet. Incremental allocation is

achieved in our system by means of the dynamic selection of a suitable task from T

by taking into consideration of the T

We call a multi-robot group (sub-team) formed to execute a particular task simul-

taneously and synchronously as a coalition [12]. In this research, we particularly deal

with the types of tasks that require same type of capabilities within a coalition to ex-

ecute a task although the overall mission requires a heterogeneous team and diverse

capabilities. Shehory and Krauss [13] present an algorithm for coalition formation in

cooperative multi agent systems. During the coalition value calculations, the capabili-

ties of agents are taken into consideration. In multi robot systems, the cost values are

a function of not only the capabilities but also the physical conditions, which change

during execution. Vig and Adams [14] state the differences of the multi-robot and the

multi-agent coalition formation issues from the sensor possessive point of view. Another

important factor in multi-robot systems is the changing cost values during runtime.

Move 1

Move 2

Drop 1

Drop 2

{Conjunctive Arc}

Clean

[reqno = 2]

[reqno = 1]

Fig.1. The Directed Acyclic Mission Graph for dropping the stamped boxes into the mailbox in

an order. The boxes (1,2) are moved to the stamping machine and then dropped. After the boxes

are moved to the stamping machine, the room can be cleaned.

3 Proposed Approach

DEMiR-CF is for multi-robot teams that must cooperate/coordinate to achieve complex

missions including tightly coupled tasks that require diverse capabilities and collective

work [1]. It combines auctions, coalition maintenance and recovery routines called Plan

B precaution routines to provide an overall system that ﬁnds (near-) optimal solutions

in the face of noisy communication and robot failures.

3.1 The Dynamic Priority-based Task Selection Scheme (DPTSS)

In our approach, the instantaneous, precedence and resource feasible decisions are made

by the robots’ global time extended view of the problem from the local perspectives.

While completion of the mission is the highest priority goal objective, additionally

other performance objectives can also be achieved. The time extended consideration

is achieved through forming the rough schedules by the robots. Since the schedules

are highly probable to change in dynamic environments and furthermore robots also

have the real time burdens of path planning, mapping etc., the schedules formed in our

approach are tentative and constructed by computationally cheap methods.

A critical task is a task that has inﬂexibility from the resources point of view and

the robot is suitable for that task. Level of a node (task) represents the depth of the node

in the mission graph in reversed order. The level of a node is assigned as the value in-

crementing by one from the maximum level of the the succeeding nodes (connected by

the conjunctive arcs). The coalition reservation tables are built for the critical tasks rep-

resenting the committed robots for the execution. Depending on the number of entries,

the possibility of mission completion can be attained. The reservation tables present

the future commitments although they are roughly determined. Each robot generates its

rough schedule as a dynamic priority queue by considering critical task set (T

), the

coalition reservation entries, the eligible tasks (T

), the conjunctive arcs and the re-

quirements. Since each robot r

has different capabilities, the eligible sets T

and the

priority queue entries may be different. Sometimes the uncertain information (e.g. re-

lated to a local online task) or the unexpected events (e.g. detection of the fuel leakage)

may result in this difference although the capabilities are the same. The rough sched-

ule generation is implemented by the Algorithm 1. curcs

represents the remaining

capacity of robot r

and reqcs(i) represents the required capacity for task t

in terms

of the consumable resources (e.g fuel). The priority queue is formed by ﬁrst taking into

Algorithm 1 Rough Schedule Generation Algorithm.

= φ; R = curcs

; T

= φ

C = T

\ T

prioritized by the level values in descending order (the tie breaking rules: type

priority and r eqno)

for each t

∈ C and t

∈ T

R = R − reqcs(i)

if R < 0 then

unachievable = true; break

else

= T

∪ t

end if

end for

if (unachievable k R − r eqcs(top(T

)) > 0 k top(T

) ∈ T

then

= top(T

)

end if

consideration of the conjunctive arcs of the task graph. If there are no online tasks, or

invalidations, the order of the tasks which are connected by the conjunctive arcs remains

the same in the priority queue although there may be additional intermediate entries in

the queue. The dynamic task selection is implemented by by using the requirements of

the rough schedule (Algorithm 2). The tie breaking rules while forming the active list

) is given from the highest to the lowest importance as follows: The least ﬂexibility

(reqno), the level value of the node, and the id. The fundamental decision that each

robot must make is selecting the most suitable action for a task from a set of active

tasks (T

) by considering T

. The four different decisions are: keeping execution of

the same task (if any), joining to a coalition, forming a new coalition to perform a free

task and being idle.

In DEMiR-CF, the standard auction steps of CNP [15] are implemented to announce

the intentions on the task execution and select the reqno number of robots for a coalition

in a cost-proﬁtable, scalable and tractable way. Additionally Plan B precaution routines

are added to check validness in these negotiation steps. Each robot intending to execute

a task announces an auction after determining the rough schedules.

Maintaining the coalition reservation entries are implemented by negotiations. The

robots maintain the coalition reservation entries by proposing the coalition commitment

requests to the speciﬁc robots that can execute the corresponding task. The coalition

reservations only show the tentative agreements which can be canceled in future.

Each robot keeps the models of the tasks and the other robots in their world knowl-

edge to track the internal and external inconsistencies. The complete set of precaution

routines to handle several contingencies can be found in [1].

Algorithm 2 DPTSS Algorithm for robot r

Determine the T

, T

⊆ T

and T

⊆ T

Maintain the coalition reservation entries for the tasks in T

Generate the Rough Schedule (T

)

Select the active task t

from T

to process and perform one of the following

if t

6= φ then

if t

is the current task then

Continue to the current execution

else

Offer an auction for forming a new coalition or directly begin execution

end if

else

if R + top(T

) ≤ curcs

and proﬁtable to join a coalition then

Join a coalition

else

Be idle

end if

4 Experimental Results

In our earlier work, we apply the rough schedule generation scheme for the MTSP

(open loop-Multiple Traveling Salesman Problem) on multi-robot systems [3]. Since

the rough schedules are generated tentatively, quality of the solution is improved over

time if the initial quality is degraded. Furthermore, an incremental assignment approach

saves a considerable computation overhead. In this work, we evaluate our approach

Table 1. The Cost Evaluations for the tasks of the application domain.

Task Type Cost Function Taken Action

Search Task Distance to the region interest points [4] In depth analysis is needed.

Intercept Task Expected time to achieve the task:

= E[dist(r

, t

)]/E[speed −

diff (r

, t

)]

Immediate response is needed. One step auction or

direct execution is applied.

in the US NAVY’s realistic simulator [16]. Particularly in this experiment, the mission

consists of the online tasks, generation time of which are not known in advance by the

robots (Autonomous Underwater Vehicles). The overall mission is searching a prede-

ﬁned area and protecting the deployment ship from any hostile intents. The initial graph

of the application mission is given in Figure 2. Initially the mission consists of only the

Search Task. Although reqno = 1 for this task, since there are no other tasks and the ro-

bots have enough fuel capacities, they execute the task as a coalition and divide the area

to search. The Search Task execution with three robots and the corresponding search

areas are illustrated in Figure 3. The robots patrol the sub-areas which are determined

after the negotiations [4]. Therefore, although there is only one task on the higher level,

Search-1 Search - 3

S T

[reqno = 1]

(a) Mission Graph

Search - 2

S T

[reqno = 1]

(b) Allocation of the Mission Tasks

Fig.2. Initial Mission graph consists of only Search Task.

−50 0 50 100 150 200 250

−50

100

150

200

250

Robot Paths and Search Areas

SA−1 SA−2 SA−3 R1 R2 R3

−50 0 50 100 150 200 250

−50

100

150

200

250

Robot Paths and Search Areas

(a) (b)

Fig.3. (a) Mission execution begins. The overall area is divided into regions related to the gener-

ated task instances. (b) Robots patrol the area in the corresponding regions.

the robots create instances of the Search Task (Search 1-3) as if each instance is another

separate task. If there are no hostile intentions, the robots only search the area.

Whenever a hostile diver is detected by the robots, a related interception task is

generated. The execution trace after detection of the hostile diver is illustrated in Fig-

ure 4. R2 chases performing the search task and immediately switches to the Intercept

Task. The hostile diver attacks to R2 by using its missiles. Therefore R2 needs to return

back to the deployment area while R1 takes control of the Intercept Task. R1 can deter

the diver but waits until the threat entirely disappears. The evolving mission graph is

illustrated in Figure 5. The robots may need to generate local tasks (e.g. Repair/Refuel

Task,) as in Figure 5 (d) making the graphs different even when they work cooperatively

for the same objective (Figure 5 (c-d)). In Figure 5 (c), although executing the Intercept

Task, R1 can make a coalition commitment assuming it will succeed in a predeﬁned

time (described as TBD), R2 cannot make any coalition commitment for the search

task because its future operations depend on its recovery time.

Cost evaluation for the tasks are implemented accordingly depending on the task.

While the robots try to optimize the fuel levels for the Search Task, the Intercept Task

requires immediate response and time minimization (Table 1). Cost evaluation for the

search task is implemented by dividing the search area into regions and evaluating the

−50 0 50 100 150 200 250

−50

100

150

200

250

Robot Paths and Search Areas

SA−1 SA−2 SA−3 R1 R2 R3 Hostile Diver

−50 0 50 100 150 200 250

−50

100

150

200

250

Robot Paths and Search Areas

SA−1 SA−2 R1 R2 R3 Hostile Diver

(a) (b)

−50 0 50 100 150 200 250

−50

100

150

200

250

Robot Paths and Search Areas

SA−1 SA−2 R1 R2 R3 Hostile Diver

−50 0 50 100 150 200 250

−50

100

150

200

250

Robot Paths and Search Areas

R1 R2 R3 Hostile Diver

Fig.4. A sample execution trace under highly dynamic task situations. (a) The robots begin

searching the area. (b) R2 recognizes the hostile intent. After detection, the hostile vehicle at-

tacks to R2. (c) R2 returns to the deployment ship. R1 takes control of the intercept task. (d) R1

and R3 continue to searching the area.

distance values for the interest points [4]. For the intercept task, the expected time to

achieve (intercept the diver) the task is taken as the cost value. The Intercept Task is

assumed to be achieved whenever the hostile threat is believed to be disappeared. The

emergency tasks are directly executed. However, in this case, parallel executions may

occur and should be resolved. This facility is provided in our framework by the Plan

B precaution routines. In a sample scenario with limited communication ranges, the

parallel executions arise for the Intercept Task as in Figure 6. However these inconsis-

tencies are resolved by the Plan B precaution routines whenever robots enter into the

communication range.

5 Conclusion

In this work, we present our dynamic and distributed task selection scheme (DPTSS)

embedded in our generic cooperation framework, DEMiR-CF. The dynamic task selec-

tion scheme ensures that the instantaneous, precedence and resource feasible decisions

are made by the robots’ global time extended views of the problem from the local per-

spectives. The framework combines a distributed auction based allocation method and

S T

(a)

S T

[reqno = 1]

Intercept

[reqno = 1]

S T

Search -1 Search -2

R1 R3

Intercept

Repair/

Refuel

Coalitional

Commitment

S T

Search -1 Search -2

R3 TBD

Intercept

S T

(a)

S T

[reqno = 1]

Intercept

[reqno = 1]

S T

(a) New Mission Graph (b) Allocations of the Mission Tasks

Search -1 Search -2

R1 R3

Intercept

Repair/

Refuel

Coalitional

Commitment

S T

Search -1 Search -2

R3 TBD

Intercept

Fig.5. Mission graph and allocations evolving through time accordingly.

50 0 50 100 150 200 250

100

150

200

250

Robot Paths and Search Areas

SA1 R1 R2 R3 Hostile Diver

Fig.6. Under limited communication ranges, parallel executions may occur to be resolved. R3

switches to the search task while R1 executes the intercept task.

Plan B precaution routines to handle contingencies and real world limitations and to

maintain the high solution quality with the available resources. The preliminary results

on complex missions, as presented in this paper, reveal the integration of real-world

task allocation and execution; immediate and effective handling of the online tasks and

events and the solution quality maintenance performance of DEMiR-CF is promising.

References

1. Sariel, S., Balch, T.: A distributed multi-robot cooperation framework for real time task

achievement. In: The Intl. Symp. on Distributed Autonomous Robotic Systems (DARS).

(2006)

2. Sariel, S., Balch, T., Erdogan, N.: Robust multi-robot cooperation through dynamic task al-

location and precaution routines. In: The International Conference on Informatics in Control,

Automation and Robotics (ICINCO). (2006)

3. Sariel, S., Balch, T.: Efﬁcient bids on task allocation for multi-robot exploration. In: The

19th International FLAIRS Conference. (2006)

4. Sariel, S., Balch, T., Stack, J.R.: Empirical evaluation of auction-based coordination of AUVs

in a realistic simulated mine countermeasure task. In: The Intl. Symp. on Distributed Au-

tonomous Robotic Systems (DARS). (2006)

5. Botelho, S.C., Alami, R.: M+: a scheme for multi-robot cooperation through negotiated

task allocation and achievement. In: IEEE Intl. Conf. on Robotics and Automation (ICRA).

(1999)

6. Zlot, R., Stentz, A.: Market-based multirobot coordination for complex tasks. Intl. J. of

Robotics Research 25 (2006)

7. Dias, M.: TraderBots: A New Paradigm for Robust and Efﬁcient Multirobot Coordination in

Dynamic Environments. Phd thesis, Carnegie Mellon University (2004)

8. Lemarie, T., Alami, R., Lacroix, S.: A distributed task allocation scheme in multi-uav con-

text. In: IEEE Intl. Conf. on Robotics and Automation (ICRA). (2004)

9. Gancet, J., Hattanberger, G., Alami, R., Lacroix, S.: Task planning and control for a multi-

uav system: Architecture and algorithms. In: IEEE/RSJ Intl. Conf. on Intelligent Robots and

Systems (IROS). (2005)

10. Dias, M.B., Zlot, R.M., Kalra, N., Stentz, A.: Market-based multirobot coordination: A sur-

vey and analysis. Technical Report CMU-RI-TR-05-13, Carnegie Mellon University (2005)

11. Brucker, P.: Scheduling and constraint propagation. Discrete Applied Mathematics 123

(2002) 227–256

12. Horling, B., Lesser, V.: A survey of multi-agent organizational paradigms. The Knowledge

Engineering Review 19 (2005) 281–316

13. Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation. Artiﬁcial

Intelligence 101 (1998) 165–200

14. Vig, L., Adams, J.A.: Issues in multi-robot coalition formation. In: Multi-Robot Systems.

From Swarms to Intelligent Automata. Volume III. (2005) 15–26

15. Smith, R.G.: The contract net protocol: High level communication and control in a distrib-

uted problem solver. IEEE Trans. on Computers C- 29 (1980)

16. (ALWSE: http://www.ncsc.navy.mil/Capabilities

and Facilities/Capabilities/

Littoral

Warfare Modeling and Simulation.htm)