A Problem Decomposition Scheme for Distributed Problem Solving
Yasuhiko KITAMURA, Shoji TATSUMI, and Takaaki OKUMOTO
Faculty of Engineering, Osaka City University
3-3-138 Sugimoto, Sumiyoshi-ku, OSAKA 558, JAPANfkitamura, tatsumi, okumotog@info.osaka-cu.ac.jp
S. Misbah DEEN
DAKE Centre, Keele University
Keele, Staffordshire, ST5 5BG, UK
misbah@cs.keele.ac.uk
Abstract
To deal with large-scale and/or geographically distributed problems, a number of expert systems should
be combined through communication networks, anddistributed problem solving (DPS) techniques are required to make such a group of expert systems works
effectively. In DPS, if a given problem can be decomposed and allocated properly, the performance will
be increased because of high parallelism and small
communication overhead. Most of DPS techniquesso far have been using such problem decomposition
knowledge in explicit or implicit ways, and suchknowledge is assumed to be given a priori. In thispaper, we proposed an automated problem decomposition scheme based on knowledge hierarchy which
can be applied to problem domains where problem
decomposition knowledge is not given a priori.

1 Introduction
To deal with large-scale and/or geographically distributed problems, a number of expert systems with knowledge bases should
be combined through communication networks, and distributed
problem solving (DPS) techniques are required to make such agroup of expert systems works effectively.
In DPS, problem solvers called agents are distributed anda given problem to be solved needs to be decomposed andallocated to all or some of them. For example, Contract Net
Protocol [8] is a communication protocol to assign problems toappropriate agents based on negotiations among agents. In thisframework, problems are assumed to be decomposed a priori byusers or designers in an explicit manner. Functionally/Accurate
Cooperative(FA/C) DPS system [6] is another canonical example of DPS technique, but problems are also assumed to be
assigned to agents implicitly before problem solving starts.
There has been little work that addresses automated problem
decomposition [2] although it shows a crucial aspect for DPS.
If a given problem can be decomposed and allocated properly,

the performance will be increased because of high parallelism
and small communication overhead among agents.
In this paper, we proposed an automated problem decomposition scheme based on knowledge hierarchy which can beapplied to problem domains where problem decomposition
knowledge is not given a priori. In our scheme, when an
agent receives a problem, referring the knowledge hierarchy,
it autonomously decomposes the problem and allocates thedecomposed subproblems to available agents. Moreover, forcases where there are several alternatives to decompose a problem, we propose several selection strategies to reduce them toone.
In section 2, we give a rigid formulation of DPS based on
the state space graph representation. In section 3, we present a
distributed inference scheme called diffusing search [4] whichis the base of our proposed scheme. When the given problem
is a large-scale one, without problem decomposition, agentswith this inference scheme have to search a huge search space
generating a big amount of communication which is almost
intractable. To cope with this drawback, we propose a problem
decomposition scheme using an example of travel planning insection 4.

2 Formulation of DPS
In this section, we present a formulation of DPS based on thestate space graph representation [1].

2.1

Problem and Solution

Non-AI problem solving can be depicted as a deterministic
process where the sequence of operators for problem solving
has been determined beforehand unambiguously, for example,
in a form of program. The process thus simply follows thesequence of operators and there are no alternative operators tochoose. On the other hand, AI problem solving can be depicted
as a non-deterministic process. The process is required tochoose an operator out of multiple alternatives and the choicemay not be always correct. When it makes a wrong choice, it
may lead to getting stuck and a way to escape from that is toget back to the point of wrong choice and to choose anotherone out of other alternatives. Therefore, AI problem solving
can be formalized as a search process which finds a path on agraph as follows.

Definition 2.4 (Joint state) For knowledge of agent a, Ka =<Sa ; Oa >, and that of b(6= a), Kb =< Sb ; Ob >, if there exists
a state s which satisfies s 2 Sa \ Sb , then s is called a jointstate of agent a and b. 2

Definition 2.5 (Joint knowledge) Joint knowledge of agent a,
JKa , is denoted as < Sa ; C > where C is a community, a set
Definition 2.1 (Problem and solution) A problem p is given of agents. This joint knowledge is said to be complete if
as 4-tuple < S; O; sI ; G > where S is a non-empty set of states,
O( S 2 S ) is a set of operators, each of them specifies a state
8s 2 Sa ; 8b 2 C 0 fag : s 2 Sa \ Sb , (s; b) 2 JKa :2
conversion, sI (2 S ) is the initial state, G( S ) is a set of goalstates. The tuple < S; O > can be viewed as a graph called
In words, a complete joint knowledge means the agent knows
state space graph. A problem is said to be finite if the state all the joint states and all the agents which share them.
space graph is finite. A solution is given as any path from theinitial state to a goal state in the state space graph. In other Redundancy Finally, we define a concept redundancy, which
words, it is a sequence of operators that converts the initial classifies overlap of knowledge among agents, as follows.
state into a goal state. 2
Definition 2.6 (Redundancy) For a community C , if it satis2.2 Agent, Community, and Knowledge Distri- fies 8a; b 2 C : a 6= b ) Oa \ Ob = ;, the community is said
to be non-redundant, and if it satisfies 8a; b 2 C : Oa = Ob ,butionthe community is said to be completely redundant. Otherwise,
DPS deals with problem solving by multiple agents. For the community is said to be partially redundant. 2
example, let us assume a system, which offers international
travel information, consisting of multiple agents. Each agent
offers information of only one country but it cooperatively 3 Diffusing Searchworks with other agents when it is asked to find an international
travel plan. As this example, the knowledge, namely a set The diffusing search [4] is an inference method for DPS basedof operators, to be required for problem solving is distributed on distributed search. The search proceeds as in a uniform
among agents. The local knowledge of each agent therefore manner and the completeness of search is guaranteed.
can be depicted as a graph which represents the range of state
conversions by the agent. More formally, we can define them
3.1 Diffusing Search System
as follows.
Before we describe the diffusing search algorithm, we clarify the
Definition 2.2 (Knowledge) The local knowledge of agent a is definition and assumptions on systems on which the algorithm
denoted by Ka =< Sa ; Oa > where Sa and Oa ( Sa 2 Sa ) are is executed.
a set of local states and local operators of agent a respectively.
A set of agents is called community and the knowledge of Definition 3.1 (Diffusing search system) A diffusing searchcommunity C is defined as KC =< SC ; OC >, where SC = system is a community composed of a finite number of agents.
a2C Sa and OC =a2C Oa , in words, that is the sum of One of agents is called the root agent aroot which submits the
local knowledge of agents in the community. 2
initial problem. 1 Each agent can communicate with any otheragents only by exchanging messages and no message are lost
We here define several concepts about knowledge distribution during communication. 2
in a community: coverage, joint state, and redundancy, thatcharacterize a community, namely a DPS system.
Generally speaking, the characteristics, the capability of
producing solutions or the efficiency of a diffusing search
Coverage As a relation between a problem and knowledge system vary depending on its knowledge distribution. In thissection, we assume a diffusing search system which satisfies
of agent or community, we define a concept coverage.
the following assumptions.
Definition 2.3 (Coverage) For a problem p =< S; O; sI ; G >and a community C , we say the knowledge of agent a(2 C ), Assumption 3.2 Problems are finite and covered by the diffusKa =< Sa ; Oa >, covers the problem if O  Oa . Likewise, ing search system. 2
we say the knowledge of community C , KC =< SC ; OC >,Assumption 3.3 Each agent has complete joint knowledge. 2
covers the problem if O  OC . 2

SS

Joint State We then introduce a concept, a joint state, that Assumption 3.4 The diffusing search system is non-redundant.
is a state shared by multiple agents and that reflects relations 2
1 A user can be the root agent.
between knowledge of an agents and that of another.

3.2 Diffusing Search Algorithm

3.2.2

The diffusing search algorithm is based on distributed searchand can be viewed as a combination of intra-agent local searchand inter-agent global search. A local search is executed by asingle agent to find partial solution paths inside its local knowledge and the global search specifies message exchange among
agents to control local searches to obtain a global solution
path. So far these two search algorithms have been investigatedindependently in AI [7] and distributed algorithm [3] respectively. We here describe how to integrate these algorithms as
the diffusing search algorithm.

The global search algorithm specifies message passing among
agents to invoke local searches to obtain a global solution.
We show below the global search algorithm of agent a as anextension of a conventional distributed search algorithm [3].

Global Search Messages– <search; >. To request a problem

 Database––

3.2.1 Local Search
The local search is based on classical search algorithm [7]and executed by a single agent. A classical search algorithm
is initiated by giving the initial state and terminated with< success > if it finds a goal state or with < failure >if it fails. In the diffusing search algorithm, the local search
can be terminated with a joint state which is a candidate ofintermediate state on a path to goal state when the agent cannot
find the goal state by itself, so we extend the classical algorithm
to the one which returns one more result < continue;JS>
where JS is a set of joint states. The algorithm of an agent a is
as follows.

CJ ( Sa ). A set of joint states that have been found.
RQ( Sa 2 C ). A set of pair lists of a local initial states andan agent which requested it. (s; b) 2 RQ means that agent b
requested a problem < s; G > to agent a.

 Algorithm<Root agent>State1 When initializing

<

s>

a

search; I to agent I which has the
Step1 Send
initial state I in its local knowledge.
State2 When receive found .

s<>

Step1 Halt.

<General agents>< search;s> from ap
s CJ
s; ap ) in RQ.
s(a) If it ends with < success > then send
< found > to all agents.
(b) If it ends with < continue;JS> then for eachof sc 2 JS , if sc 62 CJ then add sc in CJ and send
< search;sc > to all b 2 CKa(sc ).
(c) If it ends with < failure > then wait.
State2 When receive < found >State1 When receive

Step1 If 2
then wait else add (Step2 Execute local search( ).

 Database–< s; G >.

– <found>. To notify that the agent has found a goal state.

OP ( Sa). A set of open states that are candidates to be
expanded.

CL( Sa). A set of closed states that have been expanded.
– PN ( Sa 2 Sa ). A set of pointers between two states.
(si ; sj ) 2 PN means a path from si to sj has been found.
– JS ( Sa ). A set of joint states that have been found.
–

Step1 Halt.

 Function–

SS : 2OP ! OP . A function to choose a state from OP to 4
expand.

 Algorithm: local search(sLI )A Problem Decomposition Scheme
Based on Knowledge Hierarchy

In this section we describe a problem decomposition scheme
using travel planning problem as an example.

s
OP . Set JS = ;.
OP = ; then
4.1 Travel Planning(a) If JS = ; then end with < failure > else end with< continue;JS>.
Travel planning problem described here is to find a travel routeSS(OP ). Add s in CL. Remove s from OP .
Step3 sthat is spreading very wide area like an international travel
route. The knowledge required to solve this problem is very
Step4 If s 2 G then end with < success >.
large, various according to the means of transportation, andStep5 For each of s 2 Oa (s) \ O (s),geographically distributed. It is almost impossible to maintain(a) If s 62 CL [ OP then add s in OP and (s; s ) in PN .
this knowledge in a single centralized knowledge base and it is
Step6 If JKa (s) 6= ; then add s in JS .
reasonable to solve this problem by cooperations of distributed

Step1 Put LI in
Step2 If

0

0

0

0

knowledge bases, agents, each of which maintains a part of
the knowledge according to the means of transportation (bus,This algorithm is initiated by giving sLI as the local initial train, ship, aircraft, etc) or the domain it covers (inter-country,
state and terminate with a local search tree, denoted by < country, county, town, etc).
This travel planning problem can be viewed as finding a
CL; P N > which has the local initial state sLI as the root
path from a starting place to a goal place on a state spacenode.
Step7 Go to Step2.

graph where places and transportations between two places are
represented as states and operators respectively. We, therefore,
can use the diffusing search scheme to find such a path fromthe knowledge that is distributed among agents, but actually wewould face a big amount of communication overhead among
agents if we use the diffusing search algorithm naively because
the state space graph would be very big and be maintained bymany agents.
To reduce the communication, we here propose a problem decomposition scheme by using knowledge hierarchy andfurther improve the decomposition by using several selection
strategies. By this scheme, an agent does not need to submit
messages for all the joint states that are connected from thelocal initial state, but submits a message for a single selectedjoint state. Only when the selected joint state does not produce a solution, a succeeding message is submitted for anotheralternative joint state.

4.2 Knowledge Hierarchy
For our world-wide travel planning problem, we extend our
representation of a state s into a list consisting of hierarchicaldomains such as [s1 ; s2 ; . . . ; sn ]. We say si is domain name atlevel-i.
For example, we can represent the Heathrow airport as[UK; London; Heathrow], each of which represents the domainname of country, county or state, and town respectively insteadof just Heathrow as before.
By this extension, we can classify problems according to their level and domain. When a problem p =<n
1
2
[s1I ; s 2I ; . . . ; sn
I ]; [sG ; sG ; . . . ; sG ] > is given, we say p is a1
problem of domain [sI ; . . . ; siI01 ] at level-i if the following
conditions are satisfied. 2

sjI = sjG
sjI 6= sjG

if j < i
if j = iFor
example, < [UK; Staffs; Keele]; [UK; Staffs; Newcastle] >is a problem of domain [UK; Staffs] at level-3.
<[UK; London; Heathrow]; [Japan; Chiba; Narita] > is a problem of domain world at level-1. 3
We can classify operators as well as problems. We say anoperator o = ([s1p ; s2p ; . . . ; snp ], [s1q ; s2q ; . . . ; snq ]) is an operatorof domain [s1p ; . . . ; sip01 ] at level-i if it satisfies the following
condition.

sjp = sjq
sjp 6= sjq

if j < i
if j = i

We here define the following concepts.
Definition 4.1 (Separation and Hierarchy) If every operatorof an agent is a level-i operator of the same domain, then theagent is said to be separated and called an agent in the domain
at level-i. If all the agents in a community are separated, thenthe community is said to be hierarchical. 2
2 We assume a problem has only one goal state.
3 We call the domain name of level-0 world as a special case.

When a community is hierarchical, for an agent at level-i,
agents and domains at level-j (< i) are called upper agents andupper domains respectively, and agents and domains at levelj (> i) are called lower agents and lower domains respectively.
Likewise agents and domains at level-j (= i) are called peer
agents and peer domains.
Joint states in an agent also can be categorized according to
the level of agent with which they are shared. For a level-i
agent, its upper joint states are shared with level-j (< i) agents,
its peer joint states are shared with level-j (= i) agents, andits lower joint states are shared with level-j (> i) agents. In
general, an upper joint state of agent a to agent b is identicalwith a lower joint state of agent b to agent a, but as an exception,
we introduce indirect upper joint states. For an indirect upper
joint state, there exists no corresponding lower joint state in theupper agent but a path from it to a lower joint state in the otherpeer or lower agent at least.
Example 4.2 We show an example of hierarchical community
in Figure 1. In this example, there are five separated agents;
agent BA in world domain at level 1, agents BR and NE in[UK] domain at level 2, and agent PMT in [UK; Staffs] domain and LUG in [UK; London] domain at level 3. For agent
NE, agent BA is an upper agent and the upper joint stateis [UK; London; Heathrow], agent BR is a peer agent andthe peer joint state is [UK; WestMidland; Birmingham],agent PMT is a lower agent and the lower joint state is[UK; Staffs; Hanley], and agent LUG is also a lower agent
and the lower joint state is [UK; London; Heathrow]. Notice for LUG, BA can be an upper agent (whose joint stateis [UK; London; Heathrow]) even though the difference between the levels is 2. An example of indirect upper joint state is[UK; London; Euston] of BR to [UK; London; Heathrow]of BA. There is a path connects them in LUG.

4.3

Problem Decomposition

When an agent receives a problem, it can solve it if it has a pathto the goal state in its local knowledge, or it can decompose
it, for example, a problem < sI ; sG > into < sI ; sJ > and< sJ ; sG > if it has a joint state sJ . In this sense, to decompose
a problem can be viewed as to find a joint state.
As we have shown in the previous section, there
are three types of joint states; upper, peer, andlower joint states.
When a problem < sI ; sG >=<jj1n[s1I ; . . . ; sI ; . . . ; sn
]
;
[
s
;
I
G . . . ; sG ; . . . ; sG ] > of level-lp is given
to an agent at level-la , by observing the level relation between
the agent and the problem, we can select one type out of threeby using the following rules.
1. If lp < la , then choose an upper joint state sJ that is
identical with [s1I ; . . . ; slIa 01 ; slJa ; . . . ; snJ ].
2. If there is a lower joint state sJ that is identical withl +1 l +2[s1G ; . . . ; sGa ; sJa ; . . . ; sn
J ], then choose it.
3. Otherwise, choose a peer joint state sJ that is identicalwith [s1I ; . . . ; slIa 01 ; slJa ; . . . ; snJ ].

< [UK; Staffs; Stoke]; [Japan; Chiba; Narita] > andthe first one is solved by PMT and the second one is assigned
to BR. Then, BR further decomposes the partial problem
into < [UK; Staffs; Stoke]; [UK; London; Euston] >, <[UK; Staffs; Euston]; [UK; London; Heathrow] >, and< [UK; London; Heathrow]; [Japan; Chiba; Narita] >because the upper joint state [UK; London; Euston] is indi[Japan,Chiba,Narita] rect. As the level of second partial problem is 3 and its domain
is [UK; London], it is assigned to LUG, and the third one isassigned to BA as in case 1. 2

BA in world at 1

NE in [UK] at 2

BR in [UK] at 2

4.4

[UK,WestMidland,Birmingham]

PMT in [UK,Staffs] at 3

[UK,Staffs,Keele]

LUG in [UK,London] at 3

[UK,Staffs,Hanley][UK,Staffs,Stoke][UK,London,Heathrow]

Selection Strategies

In the previous section, we described how to reduce the candidates of joint states by using knowledge hierarchy. However,
we still may have several candidates and need to reduce further
to one candidate. In this section, we present several strategies
to reduce them to one.

[UK,London,Euston]Figure 1: Joint states.
When there are multiple joint states to be selected, we canuse one of several strategies described in next section for afurther selection to a single joint state.
When a joint state sJ is selected for a problem < sI ; sG >,the problem is decomposed into < sI ; sJ > and < sJ ; sG >,and the former one is solved by the agent and the latter one
is assigned to the corresponding agent with which the jointstate is shared. However, there is an exception when theselected joint state is an indirect upper joint state sIJ . In thiscase, the problem is decomposed into three partial problems
such as < sI ; sIJ >, < sIJ ; sJ > and < sJ ; sG >, and thesecond and the third ones are assigned to the appropriate agents
respectively.

By Using Local Search When no information to select a jointstate is available, the agent can select the first joint state obtainedby using the local search of the diffusing search algorithm.

By Using Predefined Knowledge A user or system designer
can specify how to decompose problems beforehand. A formatof the knowledge representation may be like a tree shownin Figure 2, that has the similar structure as the knowledge
hierarchies. A leaf nodes is a description of a joint state, shownin Figure 2(b), which includes agent name that share the jointstate, and additional parameters such as approximate travel
time, travel cost, number of transfer, etc. For example, when
the goal state of problem is [UK; Staffs; Newcastle], the jointstate to be selected is Stoke by referring this discrimination tree.
When the goal state of problem is [UK; London; Somewhere](Somewhere in London), the joint state is Euston. When
there are multiple leaf nodes for a specified domain, one joint
Example 4.3 Let
usassumeaprob- state can be selected by referring parameters. This extends thelem < [UK; Staffs; Keele]; [Japan; Chiba; Narita] > flexibility of the selection.
is given to a hierarchical community as shown in Figure 1. The
problem is sent to PMT agent at first, as it has the initial state
By Learning The information contained in the discrimination[UK; Staffs; Keele] in its local knowledge. Since the leveltree given by users or designers is static and could be incorrectof the problem is higher than that of the agent, this problem is or become out-of-date. By using leaning technique, we candecomposed and assigned to an upper agent. There are two
keep the information up-to-date or build such information fromjoint state candidates to select. Let us see each case.
scratch when there is no information given beforehand. Once an
Case1 ([UK; Staffs; Hanley]): the problem is decom- agent finds a solution, it records the result in the discrimination
posedtree for future problem solving.
into < [UK; Staffs; Keele]; [UK; Staffs; Hanley] > and< [UK; Staffs; Hanley]; [Japan; Chiba; Narita] > andthe first one is solved by PMT and the second one is assigned By Inquiring Information obtained by learning is limited
to NE. Then, NE further decomposes the partial problem into because it is a passive method only based on the results the< [UK; Staffs; Hanley]; [UK; London; Heathrow] > and agent has obtained even though the other agents may have more
< [UK; London; Heathrow]; [Japan; Chiba; Narita] > or better information. Therefore, by inquiring other agents, theand the latter one is assigned to BA.
agent can select a better joint state. On the other hand, thisCase2 ([UK; Staffs; Stoke]): the problem is decomposed scheme has to pay communication cost, and may cause chain
into < [UK; Staffs; Keele]; [UK; Staffs; Stoke] > and reactions of inquiring.

5 Conclusion
Telford

ShropsStafford

Stafford

Newcastle

Stoke

StaffsUK

LondonEustonEustonworld

Manchester

FranceGatwick
EustonProblem decomposition is an important process for effective
large-scale problem solving. In the conventional DPS techniques, the problem solving knowledge is assumed to be givena priori. In this paper, we presented a problem decomposition
scheme for cases that such knowledge is not given. In ourscheme, agents autonomously decompose and allocate problems by using the knowledge hierarchy. We also presented
several strategies for the cases where there are several alternatives for problem decomposition. For our future study, we areplanning to build a prototype to evaluate our proposed scheme.

Japan
Gatwick(a) Discrimination Tree.
[Joint State, Agent Name, Parameters](b) Leaf Node Description.

Figure 2: A discrimination tree.

References[1] Ranan B. Banerji. Artficial intelligence: a theoretical
approach. Elsevier North Holland, Inc., 1980.
[2] Alan H. Bond and Les Gasser. An analysis of problems andresearch in DAI. In Alan H. Bond and Les Gasser, editors,
Readings in Distributed Artificial Intelligence. Morgan
Kaufman Publishers, Inc., San Mateo, California, 1988.

[3] To-Yat Cheung. Graph traversal techniques and the maximum flow problem in distributed computation. IEEE
By Informing If agents inform each other, in other words,
Transactions on Software Enginerring, SE-9(4):504–512,
if they exchange their information of discrimination trees each
July 1983.
other, they can get more information to select a better jointstate. This method is useful also when a new agent joins in the [4] Yasuhiko Kitamura and Takaaki Okumoto. Diffusing incommunity, the agent can advertise what it can do by informing
ference: An inference method for distributed problem
other agents. However, informing as well as inquiring causes
solving. In S. M. Deen, editor, Cooperating Knowledge
to increase the communication overhead [5].
Based Systems 1990, pages 79–94. Springer-Verlag, 1991.

4.5 Multiple Selection[5] Yasuhiko Kitamura, Baochuang Zheng, Shoji Tatsumi,
Takaaki Okumoto, and S. Misbah Deen. A cooperative
search scheme for dynamic problems. In Proceedings
1993 IEEE International Conference on Systems, Man andCybernetics, Vol.5, pages 120–125, 1993.

Though we have discussed how to select a single joint state todecompose a problem, when it is difficult to reduce the candi- [6] Victor R. Lesser. A retrospective view of fa/c distributed
dates to one and when it seems multiple candidates have almost
problem solving. IEEE Transactions on Systems, Man,
the same possibility to lead a solution, it is possible to selectand Cybernetics, 21(6):1347–1362, November/December
multiple joint states and to assign multiple partial problems
1991.
in parallel. Moreover, in the early stage of problem solving
when information in the discrimination tree is small, to assign [7] Judea Pearl. Heuristics. Addison-Wesley, Reading, Massachusetts, 1984.
multiple problems in parallel is a way to get more information
than to assign a single one. For example, in Example 4.3,
[8] Reid G. Smith. The contract net protocol: High-level
there are two joint state candidates, [UK; Staffs; Hanley] andcommunication and control in a distributed problem solver.
[UK; Staffs; Stoke], for PMT agent, and it is possible to assign
IEEE Transactions on Computers, C-29(12):1104–1113,
the former problem to NE and the latter problem to BR.
December 1980.
However, multiple assignments increase communicationand may generate redundant process. In the above example, both of NE and BR request the same problem< [UK; London; Heathrow]; [Japan; Chiba; Narita] > to BA.
The issue of how many partial problem should be assigned
depends on the quality of expected solutions and the congestionof the communication channel, and we need a further study forthis issue including techniques to reduce redundant processes.