Distributed Heuristic Forward Search for Multi-agent Planning
Authors: R. Nissim, R. Brafman
JAIR 2014 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The following section describes an empirical evaluation of our methods. We begin by evaluating mafs, comparing it to current state-of-the-art approaches. We then describe results for mad-a*, compared to centralized cost-optimal search. We also provide scalability results for both methods, scaling up to 40 agents. Table 7.1 depicts results of mafs, map-pop and Planning-First, on all IPC domains supported by map-pop. Table 7.2 depicts the runtime, efficiency (speedup divided by the number of processors), number of expanded nodes and the average of the agents initial state h-values. In Figure 7.2.1 we can see that in both domains, mad-a* solves all problems faster than centralized a*, and can solve larger problems within the time limit. |
| Researcher Affiliation | Academia | Raz Nissim EMAIL Ronen Brafman EMAIL Ben-Gurion University of the Negev, Be er Sheva, Israel |
| Pseudocode | Yes | Algorithms 1-3 depict the mafs algorithm for agent ϕi. In mafs, a separate search space is maintained by each agent. Each agent maintains an open list of states that are candidates for expansion and a closed list of already expanded states. It expands the state with the minimal f value in its open list, which is initialized with the agent s projected view of the initial state. When an agent expands state s, it uses its own operators only. This means two agents (that have different operators) expanding the same state, will generate different successor states. Since no agent expands all relevant search nodes, messages must be sent between agents, informing one agent of open search nodes relevant to it expanded by another agent. Agent ϕi characterizes state s as relevant to agent ϕj if ϕj has a public operator whose public preconditions (the preconditions ϕi is aware of) hold in s, and the creating action of s is public. In that case, Agent ϕi will send s to Agent ϕj. Algorithm 1 mafs for agent ϕi 1: while TRUE do 2: for all messages m in message queue do 3: process-message(m) 4: s extract-min(open list) 5: expand(s) Algorithm 2 process-message(m = s, gϕj(s), hϕj(s) ) 1: if s is not in open or closed list or gϕi(s) > gϕj(s) then 2: add s to open list and calculate hϕi(s) 3: gϕi(s) gϕj(s) 4: hϕi(s) max(hϕi(s), hϕj(s)) Algorithm 3 expand(s) 1: move s to closed list 2: if s is a goal state then 3: broadcast s to all agents 4: if s has been broadcasted by all agents then 5: return s as the solution 6: for all agents ϕj Φ do 7: if the last action leading to s was public and ϕj has a public action for which all public preconditions hold in s then 8: send s to ϕj 9: apply ϕi s successor operator to s 10: for all successors s do 11: update gϕi(s ) and calculate hϕi(s ) 12: if s is not in closed list or fϕi(s ) is now smaller than it was when s was moved to closed list then 13: move s to open list |
| Open Source Code | Yes | Both settings are currently implemented and available6, and since there is full flexibility regarding the heuristics used by agents, heuristics available on FD are also available on MAFD, requiring only preprocessing of the agent s view of the problem, creating its projected view. New heuristics are easily implementable, as in FD, and creating new search algorithms can also be done with minimal effort, since MA-FD provides the ground-work (parsing, communication, etc.). Footnote 6: The code is available at http://github.com/raznis/dist-selfish-fd . |
| Open Datasets | Yes | The problems used are benchmarks from the International Planning Competition (IPC) where tasks can naturally be cast as MA problems. The Satellites and Rovers domains were motivated by real MA applications used by NASA. Logistics, Transport and Zenotravel are transportation domains, where multiple vehicles transport packages to their destination. Footnote for IPC: ICAPS. The international planning competition. http://www.plg.inf.uc3m.es/ipc2011-deterministic/. |
| Dataset Splits | Yes | In order to evaluate the scalability of mafs, we conducted experiments on the Logistics, Rovers and Satellite domains from the IPC. For each of the domains, we generated multiple problem instances, increasing the number of agents k. In Logistics, the number of cities grows linearly with k, the number of airplanes remains constant at 2, and the number of packages is always 2k. For Satellites and Rovers, the number of targets grows linearly with k, the number of available observations/locations is 2k, and the instrumentation remains constant. For every value of k, 5 different problem instances were generated. The runtime values shown are averages over all 5 of them, and the error bars correspond to the standard deviation of the sample8. |
| Hardware Specification | Yes | Experiments were run on a AMD Phenom 9550 2.2GHZ processor, time limit was set at 60 minutes, and memory usage was limited to 4GB. The experiments were run on an Intel Xeon 2.4GHZ, 48-core machine. Both configurations were run on the same machine, where for mad-a*, each agent was allocated a single processor, and a* was run on a single processor. Wall-clock time limit was set at 30 minutes, and memory usage was limited to 4GB, regardless of the number of cores used. |
| Software Dependencies | Yes | We chose Fast Downward (Helmert, 2006) (FD) as the basis for our MA framework MA-FD. FD is currently the leading framework for planning, both in the number of algorithms and heuristics that it provides, and in terms of performance winners of the past three international planning competitions were implemented on top of it. MA-FD uses FD s translator and preprocessor, with minor changes to support the distribution of operators to agents. |
| Experiment Setup | Yes | For each planning problem, we ran mafs, using eager best-first search and an alternation open list with one queue for each of the two heuristic functions ff(Hoffmann & Nebel, 2001) with preferred actions and the context-enhanced additive heuristic (Helmert & Geffner, 2008). To evaluate mad-a* with respect to centralized optimal search (a*), we ran both algorithms using the state-of-the-art Merge&Shrink heuristic9 (Helmert, Haslum, & Hoffmann, 2007). We used exact bisimulation with abstraction size limit 10K (DFP-bop) as the shrink strategy of Merge&Shrink (Nissim, Hoffmann, & Helmert, 2011). |