Keywords

1 Introduction

Multiagent system refers to a system of agents working together to reason, plan, solve problems, and make decision Here an agent can be an intelligent system, process, robot, sensor [1]. Multiagent system is applicable to various domains such as supply chain management, robotics, games, military operation, logistics, and security [2–4].

In recent years, several models and algorithms have been developed in multiagent planning (MAP). A multiagent planning problem is given a set of initial states, goal states, and actions of the agents, to find plans that transform the initial state to goal state of each agent. Typically, a multiagent plan consists of concurrent actions [5, 6]. In some domains, the problem may be decomposed into subproblems and each subproblem is assigned to a different agent [7, 8]. Unlike classical planning (single agent), very few state-of-the-art multiagent planning systems exists. A recent development is FMAP [9].

Concurrent actions come naturally in multiagent planning problems. For example, consider a two-agent domain [6] where both agents are in a room R1 and want to move into the room R2 through a single doorway. The agents have the operators ‘G’ to go through the door and ‘W’ to wait. Then possible concurrent actions would be (G, G), (G, W), (W, G), and (W, W). However, a successful plan would be obtained when one agent waits and allows the other agent to pass through the gate. Therefore, coordination is needed between the actions of different agents [10]. Concurrent interacting actions are said to consistent if there is no adverse effect of actions on to each other. Concurrent actions may have negative interaction also.

Joint actions can be considered as a special case of concurrent actions. In some planning domains, an action should be performed jointly by more than one agent to get a desired effect. For example, in order to lift a heavy table, two agents have to lift the opposite sides of the table simultaneously, i.e., both agents have to perform the same action on a particular object at the same time [11]. In this paper, we focus on multiagent planning problems involving joint actions.

Joint actions in multiagent planning raise two main issues: specification and planning. In [11], PDDL [12] is extended for specifying joint actions by including concurrent action constraints in action schema. Another approach to handle joint action is proposed in [13]. In this work, agents are encoded as parameters in action schema and necessary preconditions are added in the precondition list. However, this representation can only specify positive interaction. However, there is no multiagent planning system that can handle joint actions.

In this paper, we make an attempt in this direction to come up with a multiagent planning system that handles joint actions. For this, we propose a multiagent planning algorithm in Sect. 3. The rest of the paper is structured as follows. Section 2 presents specification of joint actions. Section 4 presents the implementation results. Conclusions are given in Sect. 5.

2 Specification of Joint Action

We discuss some approaches that extend the planning domain definition language (PDDL) to represent joint actions. PDDL is widely used to formally describe planning problems. A basic syntax of action in PDDL is as follows:

  • :action <action_name>

  • :parameter <parameter_list>

  • :precondition <precondition list>

  • :effect <effect list>

The above syntax is extended in [11] to introduce concurrent interacting actions. Two main issues that are handled include: (i) ‘who’ is performing the action and (ii) ‘what other actions’ should (not) be performed concurrently.

The first issue is handled by including an agent as a parameter in the parameter list of an action. The second issue is dealt by adding a ‘concurrent’ action list in the action schema. In the concurrent action list, all the actions that are to be performed concurrently are mentioned.

Consider a box-pushing domain with varying size of boxes. Some boxes are heavy; a single agent cannot move it. Hence, more than one agent has to perform the action ‘push’ simultaneously to move heavy boxes, i.e., a joint action should be performed to achieve the desired effect. Figure 1 shows a simple box-pushing domain with two agent and three boxes. PDDL syntax of the action ‘push’ is given below:

Fig. 1
figure 1

A Box-pushing domain with possible configuration

Full size image

  • :action push

  • :parameter (?a1-agent ?b –box ?l- location)

  • :precondition (and(at ?a1 ?l) (at ?b ?l))

  • :concurrent (and (push ?a2 ?b ?l)(not(= ?a1 ?a2))

  • :effect (not (at ?b ?l))

Other representation of joint action is proposed in [14]. In this representation, agents are specified in the parameter list and joint action preconditions are mentioned in the precondition list. There is no such additional syntax or special tag to represent concurrency.

  • :joint action push

  • :parameter (?a1-agent ?a2-agent ?b–box ?l-location)

  • :precondition (and(at ?a1 ?l)(at ?a2 ?l)(at ?b ?l)

          (not(=?a1 ?a2)))

  • :effect (not(at ?b ?l))

Joint action representation with concurrent action list can also specify the negative interaction of an action, i.e., we can also specify the actions that should not be performed concurrently. In this work, joint action is handled at the planning level. Therefore, there is no requirement of explicit representation of joint actions. To handle joint actions, we introduce the notion of capabilities of agents.

Multiagent classical planning can easily be extended to support agent’s capabilities. It is possible to handle the joint action scenario by comparing the required capability of an action at a particular state with the capability of agent performing at that time. Consider the example, Fig. 1, to move a heavy box that may involve at least two agents. The number of agents involved in the joint actions depends on the capability of the individual agents. So the number of agents need not be decided a priori.

3 Algorithm for Multiagent Planning with Joint Actions

In this section, we present the brief overview of the proposed multiagent planning algorithm. Input to the planner is given by a PDDL input problem file. Input file contains the domain description that includes the number of agents, set of actions agent can perform, and other objects in the domain. It also specifies the capabilities of each agent. Each action is associated with the required capability to perform the action. Planner agent uses a heuristic forward search to search in state space.

3.1 Description of the Algorithm

The algorithm maintains an individual state of each agent and a global state. For each agent ‘i’ it maintains an open list of states that needed to be explored and closed list of states that are already explored. For each agent it selects an action from the applicable action list of current state. Applicable action list is ordered based on heuristic values. Here the heuristic value is taken as number of different propositions in the current state and goal state. After selecting actions for all agents, it merges the effects of all agents’ selected actions to the current global state. The algorithm eventually stops when the current global state is same as the goal state. The algorithm is given below.

Pseudocode of the algorithm

In the algorithm, planner extracts the applicable action list for agent i using Applicable_Action(.) function. Applicable action list contains all the actions that can agent apply at current state (step 5). Form the Applicable action list, optimal action is selected based on heuristic value using get_optimal_action(.) (step 6). Pseudocode for get_optimal_action(.) is given below.

In the above algorithm, for each action in applicable action list of agent i heuristic value is calculated (steps 1–3). Applicable action list is sorted according to the heuristic values step (4). For each action from the sorted applicable action list, algorithm checks whether this action can be added in MA-plan or not. If so then optimal action is return otherwise no-op action is return steps (5–21).

3.2 Specification of Multiagent Plan

Planner agent generates the parallel sequence of actions for multiple agents, i.e., at particular state a set of action A = {a 1 , a 2 , a 3 .. . a n } is selected. Where a 1 is an action of agent 1, a 2 is an action of agent 2, and so on (possibly included no-op action). Sequence of the action sets A 1 ;…; A k is called a multiagent plan. This MA-plan is consistent and coordinated with respect to all agents. There can be more than one possible MA-plan for same problem instance. The planner outputs one possible MA-plan for the problem and it may be the case that it is not optimal.

For example, consider the initial state of and goal state of the box-pushing domain as shown in Fig. 1. Objective is to move all the boxes to the location2. Here box3 is heavy therefore can be move if both agents jointly perform the push action at same time. Figure 2 shows one of the possible MA-plan structures for the configuration shown in Fig. 1.

Fig. 2
figure 2

A possible MA-plan structure for the configuration shown in Fig. 1

Full size image

In the MA-plan (Fig. 2), agent1 is waiting at time T3 for agent2 to perform the joint action. At time T4, agent1 and agent2 performs the joint action ‘push’. The plan length of the MA-plan is four. For various problem instances summarized results shown in Table 1.

Table 1 Experimental results in Box-pushing domain and extended block world domain
Full size table

Here the multiagent plan would be the sequence of these concurrent actions set of agent1 and agent2, i.e., {Push(B1, location2), Move (location2, location1)}; {Move (location2, location1), Push (B2, location2)};{No-op, Move (location2, location1)}; {Push(B3, location2), Push (B3, location2)}, where the elements in a set are executed concurrently or jointly.

4 Implementation Results

We have implemented the forward search algorithm with joint action using Java. Experiments were run on the Intel core i5 with 2.53 GHz machine with 4 GB of RAM. We ran our algorithm on two domains: box-pushing domain and extended block world domain. Box-pushing domain is explained in Sect. 2.

In the block-world domain, the goal is to find a plan to rearrange blocks from the initial configuration to the goal configuration. Blocks can be put on the table or on top of each other. A block can be moved only if it is the top block; additionally, only one block can be moved at a time. It is a classical planning problem. In our experiment, we considered block world domain with multiple agents and different sizes of blocks. In this experiment, light box can be moved or pickup by single agent. However to move heavy boxes more than agent should pick up the box jointly.

We have compared the performance of our algorithm with some classical planners like black box (BB) [15] and fast forward (FF) planner [14]. Black box and fast forward takes planning problems defined in STRIPS or PDDL. We have described the domains using the joint action specification technique suggested in [14]. With some modifications in PDDL, these planners (FF and BB) can support joint action up to a certain level. Table 1 shows the implementation results.

In the table, column1 shows the number of agents in the system. Column2 shows the problem size. The notation (s, m, l) is the number of small, medium, large boxes present in the problem, respectively. A small box needs one agent to push it. A medium box requires two agents simultaneously (jointly). A large box needs more than two agents simultaneously. Column3 shows whether the centralized planner was able to generate a solution plan. Column4 shows the MA-plan length.

Experimental results show that problems having more than two agents and large objects cannot be solved by classical planners, as in the (8, 4, 2) case. It is because these classical planner search in the joint state space of all agents, which becomes exponentially large with the problem size.

5 Conclusion and Future Work

In this paper, we considered a multiagent planning problem where multiple agents with different capabilities may be involved in performing some actions. We have developed a planner that can generate such plans. We have compared the performance of our planner with some existing state-of-the-art planners on some benchmark domains. Experimental results show that some problem instances cannot be solved by the classical planners. However, the proposed planner can easily handle such problem instances. There are few multiagent planners available; none of these planners can handle joint actions. Thus, our work is a first attempt toward the development of such planners. As part of future work, we would like to develop a distributed planner capable of handling joint actions.