Independent Plan Detection

Improving Multi-Agent Planning with Unsolvability
and Independent Plan Detection
Leonardo Henrique Moreira†∗, Celia Ghedini Ralha ´ ∗,
∗Department of Computer Science, Institute of Exact Sciences, University of Braslia, Braslia/DF-Brazil
[email protected]
†Systems Development Center, Brazilian Army
[email protected]
Abstract—Multi-Agent Planning (MAP) is a challenging issue
in the field of Artificial Intelligence that has gained increasing
attention in the recent years. Because of the computational
complexity and demanding interaction among agents, the high
execution times and the volume of communication are open
problems. To address these problems, we propose a Lightweight
Coordination Multi-Agent Planning (LCMAP) approach that
includes modules to compute unsolvability and independent plans
detection, before the actual planning phase. The unsolvability
detection is employed to avoid searching for planning tasks
without solution, whereas the independent plans detection
identifies goals that can be carried out independently by
certain agents. The latter minimizes the interaction among
agents, resulting in a low communication load and lightweight
coordination during the actual planning phase. With the
proposed modules, LCMAP can perform the coordination
process and transform the MAP into multiple single-agent
planning problems. The experimental results, initially focused
on loosely coupled domains, show that LCMAP is up to 1.48×
faster than the Distributed Cooperative Multi-Agent Planning
(FMAP) approach. Compared to the FMAP performance,
LCMAP attained a reduction of up to 777× in the number of
messages exchanged among agents during the planning process.
In addition, using the benchmarks available at Unsolvability
International Competition, LCMAP detected four instances
as unsolvable problems. Therefore, the LCMAP unsolvability
module proved its efficiency considering different number of
actions and predicates.
I. INTRODUCTION
The Multi-Agent Planning (MAP) goal is to find a sequence
of actions that would lead to desirable effects. The complexity
in computing the sequence of actions depends on several
aspects, which include the number of goals, actions, agents,
and coordination processes [7], [6], [16]. The complexity
depends on the representation of the problem, that can be
exponential in search and time [7].
Multiple solutions have been proposed to the MAP problem
and the approaches can be divided in two classes. The first
class transforms the MAP problem into multiple single-agent
planning (SAP) problems, which are then delegated using
strategies such as best-cost or load balancing [2], [5], [13]. The
second class contains solutions that explore the search space
collaboratively, using multiple agents and continuously refine
plans until a solution is found [14], [15]. Regardless the used
approach, the MAP is still a complex problem that demands
investigation of new techniques to reduce the execution times.
Furthermore, the evaluation of planning problems is a
important research theme with ample room for investigation,
since the few works in this direction are related to single agent
environment [12], [8].
Thus, this work addresses the MAP problem with a novel
approach that uses a Lightweight Coordination Multi-Agent
Planning (LCMAP) method. The LCMAP method has an
unsolvability detection module to verify whether the goals
are achievable, before the actual planning is executed.
The LCMAP unsolvability module meets a recent launched
challenge of the International Planning Competition (IPC)1.
The unsolvability IPC has highlighted the importance of
testing the ability of classical automated planners to detect
when a planning task has no solution. Such verification is
important to MAP solutions that deals with more complex
problems needing to apply efficient approaches. However, the
state of the art of the MAP methods do not apply unsolvability
techniques [14], [2], [5], [15], [13].
In addition, the LCMAP method has an independent plan
detection module, that uses an efficient detection algorithm
to transform the MAP problem to multiple SAP problems.
The multiple SAP problems are then delegated to agents that
independently resolve them with low communication load. The
low level of messages exchanged among agents during the
planning execution is a challenge faced by other distributed
cooperative approaches, where agents’ privacy is a desirable
requirement [11]. In order to deal with the computational
complexity, the LCMAP employs parallelism in all phases to
efficiently use the available resources.
The main contributions of the LCMAP method can be
summarized in two parts: (i) the use of an unsolvability
and independent plan detection modules before the actual
planning phase, which avoid waste of resources and allows an
efficient execution of the planning process; (ii) the evaluation
of required cooperation that supports the goal delegation with
less communication load among agents.
The LCMAP method has been experimentally evaluated
comparing to the Distributed Cooperative Multi-Agent
Planning (FMAP). Initially, the evaluation was carried out
using loosely coupled domains and it was compared to
the FMAP results [15]. These domains, namely, rover and
1Available at http://unsolve-ipc.eng.unimelb.edu.au
2017 Brazilian Conference on Intelligent Systems
978-1-5386-2407-4/17 $31.00 © 2017 IEEE
DOI 10.1109/BRACIS.2017.29
103
Authorized licensed use limited to: WRIGHT STATE UNIVERSITY. Downloaded on February 18,2022 at 00:39:12 UTC from IEEE Xplore. Restrictions apply.
satellite cases, are commonly used by different planners. The
comparison focused on the execution times and number of
messages exchanged during the planning process. The results
show that our strategy is up to 1.48× faster than FMAP.
In addition, the LCMAP was able to reduce the number of
messages exchanged among agents during the planning in up
to 777×. To test the LCMAP unsolvability module, we used
four instances available as benchmarks at IPC. The LCMAP
detected the unsolvability of the four instances. The first two
(d1, d2) in very short time (0.04 seconds) and the other two
(d3-adl, d4-adl) in 12 seconds. The unsolvability detection
time varies according to the number of actions and predicates
of each instance. The d1 and d2 problems have only two
actions and four predicates, while the other two have eleven
actions and sixteen predicates.
The rest of paper is organized as follows: in Section 2 we
present an overview of concepts related to automated planning,
multiagent systems and MAP, including related work to the
latter; in Section 3 the MAP task is formalized to introduce the
main characteristics of the proposed approach; in Section 4 the
experimental evaluation is detailed; and finally, in Section 5,
some conclusions and directions for future work are presented.
II. BACKGROUND
Automated planning is the process of deciding which
actions must be carried out and how they must be performed in
order to achieve a set of objectives [7]. In multi-agent systems
entities called agents are able of sensing and changing the
environment through their sensors and actuators, respectively.
As intelligent computer entities, agents are autonomous, once
they can deliberate about their activities to satisfy objectives.
Whereas automated planning deals with a single agent,
MAP is concerned about a collection of entities which
cooperates during plan execution or planning process [1], [17].
In order to instantiate the deliberation process, agents
may employ techniques of automated planning, characterizing
the challenging research area of MAP, which demands
investigation applying different approaches. The first challenge
to be overcome in MAP is related to the entities coordination.
If agents cooperate through a centralized custody, a huge
number of messages may be produced for the purpose
of ensuring coordination. One possible solution for this
coordination challenge is the transformation of a MAP
problem into, as many as necessary, SAP problems. This
direction has been followed by several works [15], [2], [5],
[13]. In these works, the goals split and the distribution of them
through the available agents is a common solution, although,
different approaches and techniques are applied.
In FMAP [15], all agents are forced to solve the same
base plan, described as a subset of goals, exchanging their
results with a leader, which is elected in each iteration by
a round-robin strategy. Hence, this approach shows lack of
scalability that makes it unable of computing plans using a
great number of agents, both in loosely and tightly coupled
domains.
In other works [2], [5], [13], the planning process is
composed of an intermediate step to decide the goal each agent
must try to solve: rest-achievable, best-cost and load-balance.
In [3], authors propose a delegation method, using a contract
net protocol, capable of allocating social goals in a MAP
scenario. The applied algorithm is said to provide a higher
degree of autonomy and also satisfy privacy of each agent
during the planning process.
Despite the level of flexibility, a high coordinated method
aims to supply the deliberation step, but the initiative of
building a domain independent planning tool stumbles in the
scalability and custody problems. On one hand, in some tightly
coupled cases such as logistic, agents clearly need to cooperate
in order to achieve goals, once a single entity does not have all
the capabilities required to execute the task. By the other hand,
in loosely coupled domains, such as rovers and satellite, the
coordination can be smoothed once a single agent can satisfy
all or a subset of goals by itself.
In [17], planning problems are classified into heterogeneous
and homogeneous. This preliminary classification is the
underlying condition for identifying when cooperation is
required between agents, providing a formal approach to depict
a problem as loosely or tightly coupled. As a direct effect
of this research, when a MAP problem satisfies conditions
of having neither loops in its causal graphs nor diversity on
entities, it is shown and proven that any single agent can
achieve the goals. When this contribution is combined to MAP
transformation into single-agent based on a delegation process,
goals are distributed into available agents satisfying a best-cost
or load balance strategy. The result is a decrease of planning
time as well as the search space, due to a smaller action sets.
In summary, the goal delegation is one important aspect
that must be highlighted as it clearly allows the use of
parallelism by instantiating a simpler planning process to each
agent, considering that computational platforms have limited
resources. Once each entity must deliberate through a simpler
problem, with a smaller set of actions, constraints and effects,
the response time is redressed.
According to all cited works [15], [2], [5], [13], [17], there is
still space to new approaches in MAP research related to the
coordination process and efficient execution problems. This
gap is carefully considered in this work as described in the
following sections.
III. LCMAP DESCRIPTION
Agents in a MAP environment are characterized by Planning
Domain Definition Language (PDDL) [7] files and a planner
module. The domain file describes actuators and sensors
by which agents update and read the world state through
actions, effects, and preconditions, respectively. The problem
file is composed of predicates, which express initial knowledge
of the environment and objects, over which agents perform
actions, and goals. Lastly, the planner employs a deliberation
tool to compute an action sequence.
Since agents may have different configurations (PDDL files
and planner), in our approach, this information must be shared
104
Authorized licensed use limited to: WRIGHT STATE UNIVERSITY. Downloaded on February 18,2022 at 00:39:12 UTC from IEEE Xplore. Restrictions apply.
with a special agent that plays the central role in LCMAP (the
LCMAP agent). Privacy issue is not the focus of our work
since it is considered relevant in domains where competition
plays a special role. Therefore, our work focuses on teamwork
assuming full cooperation condition as an enhancement of
MAP. The information is collected in a tuple Π, in the same
way as formalized in [13].
An action is defined as a tuple a =< PRE, EFF >,
where each item stands for a set of predicates that describes
preconditions and effects of the action, respectively.
The LCMAP method is composed of four main modules
that provide the abilities of unsolvability and independent
plans detection, carry out delegation of plans, and execute the
actual planning. The LCMAP architecture along with the main
modules, the flow of information among agents and modules
is presented in Figure 1.
Note that in Figure 1, after receiving all information from
other agents, the LCMAP agent starts a process composed of
four phases or steps: translation, unsolvability and independent
plan detection, delegation and execution. In the translation
step, the PDDL files are parsed in order to fill the Π tuple,
and all possible predicates are generated regarding the domain
and problem definitions. Note that this procedure enhances
standard parsers. Further, the detection step computes the
unsolvability of the goals. In this phase each desirable state has
its reachability verified, and if a given state is considered not
reachable, the planning process is aborted. The detection of
independence among plans is computed in a parallel module.
The independent plan detection is computed by searching
for loops in the causal graph built to represent the planning
scenario. The detection of a cycle in this graph indicates that
a cooperation is required by agents, hence goals may not be
distributed over them.
If the planning problem is feasible with independent
plans, LCMAP follows with goals assignment to planner
agents in the delegation phase. First, an agent is chosen
considering a load balance strategy, as a potential candidate for
accomplishing the goal. The goal reachability is checked and
if possible, the goal is delegated to a selected agent. After the
goal assignment, the planning process starts and two execution
schemes may be used. In the first, the LCMAP agent can
compute all plans and send the solutions to agents. In the
second option, the LCMAP agent sends the goals, instead of
plans, allowing each entity to find its own solution using its
planner tool.
As discussed, the integration of the four phases in the
LCMAP agent extends the state of the art MAP approaches
with the additional ability of unsolvability and independent
plan detection. Hence, allowing the distribution of goals
among available agents. Algorithm 1 highlights how the four
modules interact in LCMAP agent. The block from lines 2
to 5 highlights predicate computation in the translation phase.
Following, detection activities which are depicted from lines
6 to 13, are carried out simultaneously (parallel execution)
in order to provided an efficient execution. Whenever one
of these tests fails, a failure is pointed. The final lines are
concerned of the delegation phase. Regarding both previous
tests, either goals are allocated or agents receive their plans. In
this sense, the number of messages exchanged in the LCMAP
execution is 2(n–1), where n stands for the number of agents,
since each agent sends (PDDL files) and receive (goals or
plan), namely, two messages per planner agent.
We also want to highlight that each of the LCMAP agent
modules is parallelized in order to provide efficient execution
and speed up the planing process. Sections A to D describe
each of the LCMAP agent modules.
Algorithm 1 LCMAP method
Input: Π tuple
Output: Goals assigned to agents or Failure message
1: Agents send their PDDL Files

2: for ag ∈ Agents do 3: predicates ← predicates ∪ {InitialStateag}

Translation

AssignmentTutorOnline

4: predicates ← predicates ∪ {Goalsag}
5: for a ∈ Actionsag do

6:	predicates ← predicates ∪ {P REa} ∪ {EF Fa}
7: Check1 ← F alse 8: Build Graph	Unsolvability Detection
9: if ∀g ∈ Goals, degree(g) == 0 then
10: Check1 ← T rue 11: Check2 ← F alse 12: Cooperation test
Independent Plan Detection
From [17]
13: if Cooperation is not required then
14: Check2 ← T rue 15: if Check1 ∧ Check2 then 16: for g ∈ Goals do	Delegation
17:	Allocate goal g to an agent

18: Agents receive plans or goals
19: else
20: Impossible solution
A. Translation
This module parses the input files sent by each agent to
gather information about objects, variables, actions, initial
states, and goals, which are loaded into the Π tuple. These
files are written in PDDL and must use requirements: typing,
a necessary condition that allows type names in declarations
of variables.
The translation module also computes all predicates able to
be generated in the planning problem. These predicates are
distributed into conditions before and after the execution of
the action, that is, preconditions and effects. Regarding effects,
they can also be classified into positive and negative, and the
content of each complementary set depends on the assumed
state of the predicate, true or false, respectively.
The computation of all possible predicates is done using a
Cartesian product of domains of each existing variable in the
predicate.
In spite of being easily coded, this strategy implies some
side effects but none of them impair the correctness of the
approach. The cartesian product computation generates all
possible predicates, but some of them may not be achieved
according to domain and problem characteristics, such as
action preconditions. These unachieved predicates, depicted
105
Authorized licensed use limited to: WRIGHT STATE UNIVERSITY. Downloaded on February 18,2022 at 00:39:12 UTC from IEEE Xplore. Restrictions apply.
Fig. 1. The LCMAP architecture.
as unused states, do not cause errors or incorrect solutions,
however, they demand extra evaluation, affecting the response
time. The proposed model overcomes extra computation by
exploiting parallel execution techniques.
B. Unsolvability Detection
Generally, planning algorithms perform unsolvability
analysis in runtime in which objectives are checked about
their costs [10]. Thus, planning algorithms can only detect
impossible objectives by considering heuristics, which are
performed during the deliberation process. However, LCMAP
executes it in a previous step, hence saving time and resources
by predicting impossible solution by searching of lack of agent
capabilities. LCMAP indicates the missing conditions and
hence avoids searching for an impossible solution. Whenever
a goal is considered not impossible, it means that all required
resources are available, such as action effects. On the other
hand, goals and the problem solution can only be considered
possible by showing the final plan. In this way, conjunctions of
predicates and action concurrency are handled by the planner
tool which is embedded in the proposed model.
The purpose of unsolvability detection is to verify whether
goals are not impossible. As presented in Figure 1, the
planning phase occurs after unsolvability and independent
plan detection. A goal, or a set of them, can only be
considered possible by showing an execution plan by which
they are achieved, and this activity is performed after
the unsolvability detection. However, conditions or effects
necessary for achieving the goals can be checked beforehand,
by evaluating whether they exist or not in the MAP Π tuple.
Thus, the activity performed in this phase, will define the goal
as impossible or not.
The gap between these conditions and effects relies
on constraints that influence the planning process. For
instance,during execution, there might be temporal aspects,
such as total or partial order of actions, or resource
concurrency that data flow precondition → action → effects
is not enough to illustrate. Another point, cited as threats
in [15], [14], describe a situation in which an action changes
a precondition used by another action, creating a livelock.
The first step in unsolvability detection is the process
of mapping the planning problem into a graph in which
vertexes are predicates (initial states, goals, preconditions,
positive effects), and edges are actions. An especial vertex
called VirtualInitial is inserted to gather in a single point
all predicates derived from agents initial states. It is used
to check whether there is a path from initial state to each
goal g ∈ Goals. This condition is analyzed along with the
evaluation of the degree of the vertex. In latter test it is also
possible to conclude other information about the planning
problem. First, one edge that reaches a goal stands for the
ability of an agent to produce that effect, therefore the fact of
one target vertex with no arriving edge means that the goal
can not be caused by any action. Second, when a single object
does not belong to any variable domain, the goal in which it
exists becomes unreachable.
Finally, a set of impossible goals is computed and if its
cardinality is equal to 0, that means that the planning problem
is not impossible. When the amount of elements is greater than
zero, at least one goal is unachievable due to the fact that no
action can cause such effect or by the use of an undeclared
object.
C. Independent Plan Detection
MAP approaches assume, blindly, that goal delegation is
possible [2], [3]. LCMAP evaluates this hypothesis before
assigning objectives to available agents.
The independent plan detection of LCMAP computes the
cooperation level among entities, which is important in
providing conditions for reducing coordination process and
to delegate goals. This module searches for cycles in a
causal graph that is built under the same conditions presented
in [17], using the outputs of the translation phase. The
independent plan detection module is based on [17], in which
its correctness is proved.
In this module, there are procedures that check if the
predicate remains the same after executing the action or if
its value is updated.
In the following step, a search for cycles in the graph
is performed. The presence of a loop means that there are
preconditions that are provided by effects of executing an
action. In most cases of planning problems, these cycles
frequently appear but LCMAP searches for a particular class
of them, the ones whose vertexes own predicates dealing
with agents variables. In this type, a loop has at least one
predicate (vertex) whose variable domains deals with an object
representing an agent. In other words, either entity A is waiting
for states created by itself or it is requiring one or more
preconditions provided by another entity.
In [17], a planning scenario with this characteristics is
presented. In this scenario, an agent must remove an object
from a room but doing so, the exit door is closed and it can
106
Authorized licensed use limited to: WRIGHT STATE UNIVERSITY. Downloaded on February 18,2022 at 00:39:12 UTC from IEEE Xplore. Restrictions apply.
only be opened acting over a switch located outside the room.
Besides having all the necessary capabilities to accomplish
the task, a single agent is not able to perform it once it can
not be inside and outside the room, simultaneously. This is an
example of a loosely coupled domain in which cooperation is
required among operational entities. Tightly coupled domains
represent other situation which creates the special cycle class.
Finally, if there is a cycle with at least one vertex
whose predicate deals with agents, cooperation is required.
Otherwise, goals can be delegated providing a load balance
among agents.
D. Delegation
The delegation phase distributes goals to agents satisfying a
predefined policy. Common strategies in this phase include [2]:
(i) the best-cost strategy, each goal is assigned to an agent
that can achieve that goal with the least cost; and, (ii) load
balance approaches that use algorithms such as round-robin,
which intend to assign a similar amount of goals (work) to
agents.
For each goal (g ∈ Goals), the module will check its goal
reachability. In this search, the agent, after the latest one that
received a goal, is checked whether it can reach the goal. If
this is true, the goal g is assigned to the current agent. The
process is then restarted with the next goal, and is repeated
until all goals have been delegated.
After all goals are delegated, the actual planning process
is started using one of the strategies described before:
centralized, in which the LCMAP agent computes the plans
and send them to agents; or in a decentralized way, in which
LCMAP only sends goals and agents search for a solution.
IV. EVALUATION
Initially, LCMAP method was evaluated regarding
loosely-coupled domains. In this sense, rover and satellite
cases from the IPC benchmark were used. The experiments
compared LCMAP to FMAP [15]. Although there are others
MAP tools, such as [2], [4], just a small amount of works
offers codes or executable program for downloading. This
fact was the key reason for chosing FMAP, since there is
a developed tool for downloading2. The planner used in
delegation module was Fast-Forward [9] and delegation
modules used round-robin strategy. The platform used was a
Intel Core i5 with 2 CPU cores and a 2-way hyper-threading
with 6GB RAM.
The first experiment evaluated the performance
improvement with the parallel execution. Eight agents
were used for both cases and execution times (in seconds)
were measure in order to compute speedup metric3.
LCMAP parallel execution improved performance up to
1.752× and 1.326× in each case. Besides that, the speedup
metric was improved as the number of threads increased.
Hence, the time spent in the whole process decreased. This
2Available at http://users.dsic.upv.es/grupos/grps/tools/map/fmap.html
3Speedup = TT ((1) p) , where T(1) is time spent by one processor and T(p)
is the one spent by p processors.
is an important observation once the first three phases of the
method explore parallel execution in a centralized way by
sharing local memory.
Results also showed that translation and independent
task detection took the most part of total execution time.
Considering only the second phase, the parallel execution
provided a speedup of 1.95 and 1.736 in rover and satellite
domains, respectively.
Delegation results showed an anomalous behavior because
the increase of the number of threads harmed the time spent
in this stage. The main reason for that was the planner
(Fast-Forward), that is a multi-thread tool. Therefore, when
multiple instances were launched, all of them competed for the
resources and this effort required more time spent in context
switching, leading to a performance reduction.
In the next evaluation, the LCMAP performance was
compared against FMAP. Considering that test environment
provided four threads and, in order to ensure fair conditions to
both approaches, only four entities were used because the later
planner required one thread per agent. Multi-agent scenario
was satisfied by using at least two agents and LCMAP used
a maximum parallel schema (4 threads).
In this context, the approaches had their total time and
the average number of exchanged messages spent in planning
process evaluated with the purpose of checking a normal
use case. Again, domain and satellite domains were used
as working scenarios. For each case, the data from three
simulations of each configuration, namely 2, 3 and 4 agents,
was collected. Table I presents the results, which are computed
as the average of metric values.
TABLE I
PERFORMANCE COMPARISON

Domain	Approach	Time [s]	Messages
Rover	LCMAP	13.725	4
FMAP	20.35	3109.92
Satellite	LCMAP	2.499	4
FMAP	3.214	204.69

Considering planning time, FMAP was 1.48× and 1.29×
worse than our proposal in rover and satellite domains,
respectively. In spite of having two extra phases, unsolvability
and independent plan detection, LCMAP showed a better
performance due to its effort of eliminating coordination
before the planning process. On the other hand, the greatest
portion of the execution time spent by FMAP was spent by this
process. LCMAP showed an outstanding reduction of message
bottleneck due to its constant number of exchanged message,
namely 2(n – 1) per agent, when agents send their PDDL
files and receive plan or goals. Once LCMAP used an average
number of 4 communications, FMAP had to exchange up to
777× more messages with only four agents.
In the following analysis, both approaches were evaluated
about their performance when the planning problem could not
be solvable. In other words, at least one goal was impossible.
In order to simulate this situation, one single action in each
domain had one of its effects eliminated. Results, computed as
107
Authorized licensed use limited to: WRIGHT STATE UNIVERSITY. Downloaded on February 18,2022 at 00:39:12 UTC from IEEE Xplore. Restrictions apply.
the same way of the previous evaluation, showed that LCMAP
detected that it was impossible to solve the planning problem
in 3.674 and 1.251 seconds for rover and satellite domain,
respectively. On the other hand, FMAP did not show any
warning or interaction with the user, in order to inform the end
of its execution. Therefore, it was decided to measure the time
in which logging messages were generated and after around
three minutes, an error was printed and after that, no more
recordings were done. However, the application remained
opened but completely locked. In this condition, the results
of LCMAP were 48.99 and 143.88 × better than FMAP.
Lastly, the examples of unsolvable instances found in IPC
were tested only with LCMAP. According to the descriptions
of the problems, the first two are small instances detected by
almost all planners and latter two are greater ones. Instances
d1 and d2 were considered impossible in very short time
(0.04 seconds) and highlight the observation about their
complexity. However, this condition was computed by the
earlier unsolvability plan detection module instead of the
planner tool. This fact must be emphasized to demonstrate
that the ability detection derives from a novel contribution of
the LCMAP model. Actually, the planner tool, which runs in
delegation phase, was not even started once the unsolvability
was previously detected. Instances d3-adl and d4-adl had a
slower detection due to their more detailed description (12
seconds). Once these problems are composed of eleven actions
and sixteen predicates, the first instances use only two actions
and four predicates.
V. CONCLUSION
In this paper, the LCMAP method is based on agent
communication with a small number of messages and
four modules that provide the ability of unsolvability and
independent plan detection. The LCMAP phases include the
translation module, where all information is processed in order
to feed the next stages. Unsolvability and independent plan
detection phases are evaluated in parallel, avoiding waste of
time and resources when searching for an impossible solution.
Only after that, planning process is started by assigning goals
to agents according to a round-robin strategy.
Our approach shows that it is possible to reduce the
message bottleneck generated in coordination process by
delegating goals to agents whose sequence of actions can
be computed without interaction among involved entities.
Another contribution of the proposed method is its module
of unsolvability detection, one of the latest challenges created
by IPC. The independent plan detection module identifies
goals than can be carried out independently by agents
which minimizes the interaction among agents, reducing the
communication load. In addition, all proposed algorithms are
designed to explore efficiently parallel execution in order to
improve performance.
Experimental evaluations include the comparison of
LCMAP to FMAP. The results show that LCMAP is up to
1.48× faster with a reduction of 777× in the exchange of
messages during the planning process. The message bottleneck
reduction and the parallel execution indicate that our approach
provides opportunity for scalable execution. The unsolvability
module of LCMAP was tested with four instances of the
IPC, involving different number of actions and predicates.
As a result, the four instances were efficiently identified as
unsolvable ones.
As future works, we suggest the exploitation of a higher
level of parallelism in translation, unsolvability, independent
plan and delegation modules by updating algorithms in order
to use not only local shared memory, but remote resources
in a multi-agent system. Another interesting point is the
performance and scalability evaluation in a more robust
environment, such as clusters or high-performance computing
platforms. Experimental comparisons with other planners,
more complex and tightly coupled domains, and optimization
of translation module, are also important research follow-ups.
REFERENCES
[1] I. Andres and L. N. de Barros. Using the causal graph to enhance
translations to solve contingent planning problems. In 5th Brazilian
Conf on Intelligent Systems, BRACIS 2016, Recife, Brazil, October 9-12,
2016, pages 67–72, 2016.
[2] D. Borrajo. Multi-Agent Planning by Plan Reuse. In Proc. 12th Int.
Conf. on Autonomous Agents and Multiagent Systems, pages 1141–1142.
IFAAMAS, 2013.
[3] R. C. Cardoso and R. H. Bordini. A Distributed Online Multi-Agent
Planning System. In ICAPS Proc. 4th Workshop on Distributed and
Multi-Agent Planning, pages 15–23, 2016.
[4] S. S. Chouhan and R. Niyogi. Mapja: Multi-agent planning with joint
actions. Applied Intelligence, pages 1–15, 2017.
[5] M. Crosby, A. Jonsson, and M. Rovatsos. A Single-Agent Approach
to Multiagent Planning. In Proc. 22nd European Conf on Artificial
Intelligence, pages 237–242, 2014.
[6] J. S. Dibangoye, C. Amato, O. Buffet, and F. Charpillet. Exploiting
Separability in Multiagent Planning with Continuous-state MDPs. In
Proc. 13th Int. Conf. on Autonomous Agents and Multiagent Systems,
pages 1281–1288. IFAAMAS, 2014.
[7] M. Ghallab, D. Nau, and P. Traverso. Automated Planning and Acting.
Cambridge University Press, 2016.
[8] A. Herzig, V. Menezes, L. N. de Barros, and R. Wassermann. On the
revision of planning tasks. In Proc of the Twenty-first European Conf
on Artificial Intelligence, pages 435–440. IOS Press, 2014.
[9] J. Hoffmann and B. Nebel. The FF Planning System: Fast Plan
Generation Through Heuristic Search. Journal of Artificial Intelligence
Research, 14:253–302, 2001.
[10] Y. Lesperance, H. J. Levesque, F. Lin, and R. B. Scherl. Ability and ´
knowing how in the situation calculus. Studia Logica, 66(1):165–186,
2000.
[11] S. Maliah, R. I. Brafman, and G. Shani. Increased privacy with reduced
communication and computation in multi-agent planning. In ICAPS
Proc. 4th Workshop on Distributed and Multi-Agent Planning, pages
106–112, 2016.
[12] M. V. Menezes, L. N. de Barros, and S. do Lago Pereira. Planning task
validation. In Proc. of the ICAPS Workshop on Scheduling and Planning
Applications, pages 48–55, 2012.
[13] L. H. Moreira and C. G. Ralha. Transforming Multi-Agent Planning Into
Single-Agent Planning Using Best-cost Strategy. In Proc. 5th Brazilian
Conf on Intelligent Systems, pages 462–467. IEEE, 2016.
[14] A. Torreno, E. Onaindia, and O. Sapena. An approach to multi-agent
planning with incomplete information. In Proc. 20th European Conf on
Artificial Intelligence, volume 242, pages 762–767. IOS Press, 2012.
[15] A. Torreno, E. Onaindia, and O. Sapena. FMAP: Distributed Cooperative
Multi-Agent Planning. Applied Intelligence, 41(2):606–626, 2014.
[16] N. K. Ure, J. P. How, and J. Vian. Randomized coordination search for
scalable multiagent planning. In Proc. 14th Int. Conf. on Autonomous
Agents and Multiagent Systems, pages 1793–1794. IFAAMAS, 2015.
[17] Y. Zhang, S. Sreedharan, and S. Kambhampati. A Formal Analysis of
Required Cooperation in Multi-Agent Planning. In Proc. 26th Int. Conf.
on Automated Planning and Scheduling. AAAI, 2016.
108
Authorized licensed use limited to: WRIGHT STATE UNIVERSITY. Downloaded on February 18,2022 at 00:39:12 UTC from IEEE Xplore. Restrictions apply.

• Assignment status: Already Solved By Our Experts
• (USA, AUS, UK & CA PhD. Writers)
• CLICK HERE TO GET A PROFESSIONAL WRITER TO WORK ON THIS PAPER AND OTHER SIMILAR PAPERS, GET A NON PLAGIARIZED PAPER FROM OUR EXPERTS

QUALITY: 100% ORIGINAL PAPER – NO PLAGIARISM – CUSTOM PAPER