Multi-State Commitment Search
Yasuhiko Kitamura*, Makoto Yokoo**, Tomohisa Miyaji*, and Shoji Tatsumi**Faculty of Engineering, Osaka City University
3-3-138 Sugimoto, Sumiyoshi-ku, Osaka 558-8585, Japanfkitamura,miya,tatsumig@kdel.info.eng.osaka-cu.ac.jp**NTT Communication Science Laboratories
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237, Japan
yokoo@cslab.kecl.ntt.jp
Abstract
optimal solution in an allowable time period than
We propose the Multi-State Commitment (MSC)
method to speed-up heuristic search algorithms forsemi-optimal solutions. The Real-Time A* (RTA*)
and the Weighted A* (WA*) are representative heuristic search algorithms for semi-optimal solutions andcan be viewed as a single-state and an all-state commitment search algorithms respectively. In these algorithms, there is a tradeo between the risk of making wrong choices in search process and the amountof memory for the recovery, with RTA* and WA* being the extremes. The MSC method introduces a moderate and exible characteristic into these algorithms
and can increase the performance dramatically in problems such as the N-puzzle. In this paper, by introducing a commitment list, we show a modi cation of
RTA* and WA* to their MSC versions without violating their completeness. Then, we experiment with
their performance in maze and N-puzzle problems, anddiscuss conditions that the MSC method is e ective.

1 Introduction
Problem solving in arti cial intelligence can be formalized as a search process to nd a solution path from theinitial state to a goal state in a given state space graph.
However, as the size of the state space graph increases,
it becomes dicult for a simple search algorithm tond a solution with a practical amount of time andmemory. To overcome this drawback, heuristic searchalgorithms such as the A* algorithm have been proposed that incorporate heuristic knowledge into theirstate evaluation functions [12].
Although the A* algorithm guarantees nding an
optimal solution, it is more practical to nd a semi-

to nd an optimal solution taking more time. Suchsemi-optimal solution search algorithms include theWeighted A* (WA*) [12] and the Real-Time A*(RTA*) [8].
There is an apparent di erence in the RTA* andWA* algorithms for nding a state to expand. WA*
stores all the states in its search front as its expansion
candidates, but RTA* reduces its candidates to only
child-states of the previously expanded state. Froma viewpoint of commitment in search process, RTA*
is a single-state commitment (SSC) search because it
limits the range of further search to descendants of asingle state which has been just expanded. On theother hand, WA* is an all-state commitment (ASC)search since it does not limit the range at all.1
A semi-optimal solution search algorithm generally
repeats a decision to choose a state to expand among
one or more candidates, but a wrong choice may makethe search to a goal state longer or infeasible. Hence,a SSC search like RTA*, which commits its further
search to a single candidate, tends to degrade its performance because of making wrong choices. On theother hand, for easy recovery from wrong choices, it
may be a good method to store all the candidates in
the OPEN list as in WA*. However, this method canquickly consume memory as the search front spreads
out and may actually make it infeasible to nd a solution. Hence, there is a tradeo between the risk ofmaking wrong choices and the cost of memory for recovery, and SSC, such as RTA*, and ASC, such as
WA*, are the extremes.
In this paper, we propose the Multi-State Commitment (MSC) method, that has a parameter n, which

1 It can be viewed as a no-state commitment search because
committing all states is equivalent to committing no state.

introduces a moderate and exible characteristic to
SSC and ASC. SSC and ASC are identical to MSC
when n = 1 and n = 1 respectively. MSC is exible
to balance the risk of making wrong choices and thecost of memory for recovery by changing n. In the following sections, we describe an incorporation of commitment list into the WA* and RTA* algorithms tomodify them to their MSC versions without violating
their completeness. Then, we apply these MSC searchalgorithms to maze and N-puzzle problems and show
its remarkable e ect on N-puzzle problems. Finally, we
discuss conditions that MSC shows good performancesand refer to related work.

2 Heuristic Search
A problem is given as a quadruplet hS; O; s0; Gi where
S(6= ) is a set of states, O is a set of operators, s0 (2S) is the initial state, and G( S) is a set of goalstates. The tuple hS; Oi is called its state space graph.
A child-state s is generated by applying an operatoro = (s; s ) to a state s. A state is said to be expanded
when all of its child-states are generated.
A sequence of states obtained by successive operator
applications is called a path, and a solution (path) is apath from the initial state to a goal state. If a searchalgorithm is able to nd a solution when there is atleast one, the algorithm is said to be complete. When acost (> 0) is given to each operator, the solution cost isde ned as the cost sum of the operators that construct
the solution. A solution with cost c is optimal if there
is no solution with cost less than c.
Heuristic search algorithms utilize a state evaluation
function, or heuristic function, h(s) that estimates theleast distance from the state s to a goal state. When it
does not overestimate the real distance, the heuristic
function is said to be admissible.
00

3 Multi-State Commitment WA*
3.1 WA* algorithm

In the evaluation of a state s, the A* algorithm uses
f(s) = g(s)+h(s) where g(s) is the estimated cost fromthe initial state to s, and WA* uses a weighted versionof f(s), namely f(s) = (1 , W)g(s) + Wh(s) where
0  W  1. Generally, as W increases, WA* nds asolution quicker but the solution quality worsens. In
this paper, since we mainly have interest in the search
speed for a semi-optimal solution, we deal with casesof W = 1 only in the following discussion.
Like A*, WA* uses two lists called an OPEN anda CLOSED lists. Generated states are stored once in
the OPEN list and expanded states are moved into theWA*
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: add(OPEN; successors(s));
5: add(CLOSED; s);6: if OPEN =  then return failure;
7: s get min(OPEN);
8: goto 2;
Figure 1: WA* algorithm.
CLOSED list, so it is guaranteed that generated states
are in either the OPEN or CLOSED list. Hence, WA*
is able to avoid generating an identical state twice bychecking these lists.2
We show a WA* algorithm in Figure 1. WA* begins
with the initial state (Line 1). It expands a state andgenerates child-states, but it does not generate any
states which are in OPEN or CLOSED (Line 2). If
there is a goal state in generated states, then it ends
with success (Line 3). Otherwise, it adds generated
states to OPEN (Line 4) and the expanded state to
CLOSED (Line 5). If OPEN is empty, then the searchends with failure (Line 6). Otherwise, it chooses astate with the lowest h from OPEN (Line 7), and repeats the process (Line 8). Hereafter, these operations
are counted as a single step.

3.2 MSC-WA* algorithm
WA* is an ASC search algorithm because it stores all
the generated states in the OPEN list and chooses an
expansion state from there. The Multi-State Commitment WA* (MSC-WA) limits the number of candidates to n, so we introduce a COMMITMENT list
into WA* and modify it so that generated states areadded to COMMITMENT, not OPEN, and an expansion state is chosen from COMMITMENT. MSC-WA*
maintains the length of COMMITMENT at less thanor equal to n. When the length is greater than n, it
moves states to OPEN in a decreasing order from thehighest h. If less than n, it moves states from OPEN
in an increasing order from the lowest h while OPEN is
not empty. Operations in CLOSED are the same as in
WA*. Hence, even in MSC-WA*, it is guaranteed thatgenerated states are in the COMMITMENT, OPEN,
2 When we have interest in the solution quality, WA* should
regenerate a state (move a state from the CLOSED list to the
OPEN list) when its f is improved. In this paper, we have moreinterest in the search speed and a xed f (s)(= h(s)), so we do
not incorporate such operations into the algorithm.

MSC-WA*
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: add(COMMITMENT; successors(s));
5: add(CLOSED; s);
6: while length(COMMIT MENT) > n do
7:s get max(COMMIT MENT);
8:
add(OPEN; s);
9: while (length(COMMIT MENT) < n) and
10:(OPEN 6= ) do
11: s get min(OPEN);
12: add(COMMITMENT; s);13: if (COMMIT MENT = ) then return failure;
14: s get min(COMMIT MENT);
15: goto 2;

RTA*
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: update h(s);5: if successors(s) =  then return failure;
6: s get min(successors(s));
7: goto 2;

Figure 2: MSC-WA* algorithm.

RTA*, proposed by Korf [8], is a semi-optimal solution search algorithm which interleaves a look-ahead
search and a move. By increasing the depth of thelook-ahead search, the solution quality is improved.
Since we mainly have interest in the search speed, we
set the depth at 1 in the following discussion. RTA*
do not use a CLOSED list like WA*, but it updates
heuristic values during its search process to guarantee its completeness. We show the RTA* algorithm in
Figure 3.
RTA* begins with the initial state (Line 1) and thengenerates all the child-states as expansion candidates.
When the heuristic value of a child state is 1, it isremoved from the candidates (Line 2). If a goal stateis included in the candidates, RTA* ends with success(Line 3). It will otherwise update the heuristic valueof the expanded state s to second-best c(s; s ) + h(s )in those candidates where s is one of the child-statesof s. When there is only one or no child-state, theheuristic value is set to be 1 because the expanded
state is not on any solution path and does not need
be expanded again (Line 4). If there is no following
expansion candidate, RTA* ends with failure (Line 5).
It will otherwise choose a state with the lowest h ofthe candidates and expand it in the next step. Ties
are broken randomly (Lines 6 and 7).
It must be noted that there are two alternative interpretations of the RTA* algorithm. One interpretationis that this algorithm is a fast search algorithm thatcan produce a semi-optimal solution rapidly. Anotherinterpretation is that this is an on-line algorithm suchthat an agent is interleaving planning and actions in
the real-world. In this paper, we employ the former interpretation, and try to further improve the eciencyof the RTA* algorithm.

or CLOSED list. We show a MSC-WA* algorithm in
Figure 2.
MSC-WA* does not generate child-states which arein either of COMMITMENT, OPEN, or CLOSED(Line 2), and adds generated states to COMMITMENT (Line 4). It adds the expanded state to
CLOSED (Line 5). The length of COMMITMENT
list is maintained at less than or equal to n (Line 612). If COMMITMENT is empty, then it ends with
failure (Line 13). Otherwise, it chooses a state withthe lowest h from COMMITMENT for the next expansion(Line 14). Ties are broken randomly.
MSC-WA* is equivalent to WA* when n = 1.

3.3 Completeness of MSC-WA*

Here we show that MSC-WA* is complete. The completeness of WA* is guaranteed when there is at least apath from the initial state to a goal state and the state
space graph is nite. This is because WA* does not
fall into an in nite loop as it does not expand an identical state more than once, and because also it keeps
at least a state on a solution path in the OPEN list
before it terminates.
As with WA*, MSC-WA* terminates without falling
into an in nite loop because it does not expand an
identical state more than once. If it ends with failure,
COMMITMENT must be empty (Line 13), and OPEN
also must be empty because of the operations in Lines
9-12. However, since at least one state is on a solution
path in COMMITMENT or OPEN, they cannot be
simultaneously empty, and MSC-WA* never ends infailure. Hence, MSC-WA* is complete when there is

Figure 3: RTA* algorithm.
at least a solution and the state space graph is nite.

4 Multi-State Commitment RTA*
4.1 RTA* algorithm

0

0

0

MSC-RTA*
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: update h(s);5: add(COMMITMENT; successors(s));
6: while length(COMMIT MENT) > n do
7:
remove max(COMMIT MENT);
8: if COMMIT MENT =  then return failure;
9: s get min(COMMIT MENT);
10: goto 2;
Figure 4: MSC-RTA* algorithm.

4.2 MSC-RTA* algorithm
RTA* is a SSC search algorithm that limits the candidates for the next expansion to descendants of a single
state. Here we enlarge the range by modifying RTA*
to MSC-RTA*. As with MSC-WA*, we incorporate a
COMMITMENT list into RTA* and store some of generated states in the list as expansion candidates. The
length of COMMITMENT is maintained at less thanor equal to n. When it is greater than n, MSC-RTA*
removes states from COMMITMENT in decreasing order from the highest h. We show a MSC-RTA* algorithm in Figure 4.
Lines 5 through 8 in Figure 4 of MSC-RTA* are substituted for line 5 and 6 in Figure 3 of RTA*. Namely,
each of generated states is stored once in the COMMITMENT list if it is not in it (Line 5). The length of
COMMITMENT is maintained at less than or equal
to n. If it is greater than n, MSC-RTA* removes statesfrom COMMITMENT in a decreasing order from thehighest h (Lines 6 and 7). Then, if COMMITMENT
is empty, it ends with failure (Line 8). It will otherwise choose a state with the lowest h from COMMITMENT for the next expansion. Ties are broken
randomly (Line 9).
MSC-RTA* is equivalent to RTA* when n = 1.

4.3 Completeness of MSC-RTA*
RTA* is complete when, a goal state is reachable fromall the states, the initial value of every h is nite, andthe state space graph is nite [8].
We here show that the completeness of RTA* is preserved even if we modify it into MSC-RTA*. Because
the initial value of every h is nite and there is at leasta path from the initial state to a goal state, MSC-RTA*
never fails with the in nite h value of every states surrounding the goal state.

MSC-RTA* never falls into an in nite loop becauseof the following reasons. If it fell into an in nite
loop, a goal state could not be on the loop. The hvalue of an expanded state s is updated to second-best
h(s ) + c(s; s ) where s is a child-state and c(s; s ) is
greater than 0, so the updated h value is greater thanthe best h among its child-states. Hence, every tripof MSC-RTA* around the in nite loop increases thelowest h on the loop so the h values of all states on
the loop increase without bound. At some point, since
the h value of a state on the loop will be greater thanthat of a state not on the loop, the algorithm will escape from the loop. The number of states is nite, so
it eventually reaches a goal state. MSC-RTA* is complete because this characteristic is preserved for every
n.
0

0

0

0

5 Experimental Performance Analysis
To evaluate the performance of the MSC method, we
executed experiments using maze and N-puzzle problems.
A maze is a 120  120 grid space where the entrance
is located at (0,0) and the exit is located at (119,119),and its solution is a path from the entrance (initialstate) to the exit (goal state). In the grid space, obstacles are located randomly at a ratio of 40%. There
are four operations; moving UP, DOWN, RIGHT, and
LEFT, with the cost of 1. The heuristic function ofa state is given as the Manhattan distance from it to
the goal state.
For the N-puzzle, we use a 48-puzzle with 48 numbered tiles arranged on a 7  7 board. The goal is
to transform the given initial state to the goal state,
where the tiles are sorted, by sliding tiles onto an
empty square. There are four operators that movethe empty square UP, DOWN, RIGHT, and LEFT,
with the cost of 1. The heuristic function of a state isgiven as the Manhattan distance's sum of misplaced
tiles.
We prepared 100 mazes with randomly generated
obstacle patterns and with at least a solution, and 100
solvable puzzles with di erent initial patterns. Changing n, we executed 100 trials for each combination of
MSC-RTA* or MSC-WA* and a problem. Since there
is a memory bound for the computer used in the experiments, we aborted the algorithm when the numberof states in all lists exceeded 1.5 million.
We show the obtained results of MSC-WA* in Table 1 (maze) and Table 2 (puzzle) and those of MSCRTA* in Table 3 (maze) and Table 4 (puzzle). The
gure in parentheses after the algorithm name represents n. The Success Rate is the percentage of suc-

cess without abortion due to the memory bound. The
Search Steps and the Solution Length are the averagesof successful trials.
In maze problems, neither of MSC-WA* or MSCRTA* show any remarkable improvement for any n.
In puzzle problems, on the contrary, both algorithms
showed remarkable improvements. In contrast to
WA*, which solved only 10% of the problems due tothe lack of memory, MSC-WA*, with n = 4, solved
all the problems. It is interesting that n = 4 had thebest result and more or less than that makes the performance worse. The performance of WA* looks wellconcerning the solution length, but this means WA*
found only short solutions and failed with abortion forlong ones.
In experiments with MSC-RTA*, RTA* could solve
none of the problems, whereas, MSC-RTA*, with n =2 through 6, solved all of the problems. The performance was best when n = 3, and it degraded when n
was greater or less than 3.
Due to the length of this paper, we omitted the results of 24-, 35-, and 63-puzzles, however, the algorithms showed similar performance and we believe thisdramatic performance improvement can be achieved in
any N-puzzles.

6 Discussion
The experimental results in the previous section show
the MSC method improves the search performancedramatically in N-puzzle problems. On the other
hand, it does not improve the performance in mazeproblems. In the following subsections, we discuss
about the following questions.

 Why is the MSC method e ective at N-puzzles,

but not at mazes?
 Why is the performance improvement at Npuzzles so devastating?

6.1 Wrong Choice and Recovery

A semi-optimal solution search algorithm repeats a
choice of an expansion state from one or more candidates and a wrong choice makes the search process
longer or infeasible. Since a SSC search algorithm like
RTA* limits the candidates to a single state, a wrong
choice may cause a fatal result. On the other hand, because an ASC search algorithm like WA* stores all of
the candidates, it expands the search front widely andconsumes too much memory space in nding a solution
actually. A MSC search algorithm is somewhere in the
middle of these two methods and is balanced between

S0

S1

S2

SG(S2)
SG(S1)

SG

Figure 5: A search graph.
the risk of making wrong choices and the amount ofmemory for recovery by changing n, which is the maximum length of commitment list.
Here we explain the problems where MSC shows
better performance than SSC by using a search graphshown in Figure 5. This search graph has an initialstate s0 with two child-states s1 and s2 . Each of thesechild-states starts a partial graph search of SG(s1 ) andSG(s2 ) respectively. We assume the search in SG(s1 )takes a long time to reach a goal state sG while that inSG(s2 ) takes a short time. We also assume the heuristic function is misleading, namely h(s1 )  h(s2 ), andcauses a wrong choice.
In this problem, SSC behaves as follows. It begins
with s0 and generates the child-states s1 and s2 . Then,it chooses s1 as the next state to expand due to themisleading h, proceeds to the search in SG(s1 ), andtakes a long time to reach a goal state.
On the other hand, MSC behaves as follows. As
with SSC, it begins with s0 , generates the child-statess1 and s2 , and chooses s1 as the next state to expand.
However, it stores s2 in the commitment list as anothercandidate. Hence, since h(s2 ) eventually becomes theminimum in the commitment list during the search inSG(s1 ), MSC aborts the search in SG(s1 ), restarts itfrom s2 , and reaches the goal state.
Hence, if MSC can abort the search in SG(s1 ), it
shows a better performance than SSC. In other words,
it is required that s2 has been stored in the commitment list and h(s2 ) becomes lowest in it before terminating the search in SG(s1 ). Generally, a larger nraises the probability that s2 is stored.
On the other hand, MSC may cause a side e ectTable 1: Performance of MSC-WA* in maze.
Algorithm

Success
SearchSolution
Rate
Steps
LengthMSC-WA*(1)100 1233.4 (728.0) 383.2 (58.3)
MSC-WA*(2)100 1228.8 (717.0) 374.1 (55.3)
MSC-WA*(3)100 1223.2 (708.4) 373.6 (55.9)
MSC-WA*(4)100 1232.6 (712.3) 373.8 (55.5)
MSC-WA*(5)100 1231.1 (710.3) 373.3 (55.2)
MSC-WA*(6)100 1223.2 (712.6) 373.3 (55.3)
WA*
100 1229.9 (713.4) 373.5 (55.7)
Figures in parentheses are standard deviations.

Table 2: Performance of MSC-WA* in puzzle.
Algorithm

Success
SearchSolution
Rate
Steps
LengthMSC-WA* (1)38 370374.0 (154466.0) 9495.0 (3554.9)
MSC-WA* (2)97 190507.0 (142192.3) 9470.7 (2773.3)
MSC-WA* (3)98 134848.0 (106015.8) 10180.7 (3433.3)
MSC-WA* (4)100 120051.0 (93780.7) 11138.1 (3919.0)
MSC-WA* (5)96 133266.0 (116221.0) 11584.8 (5316.8)
MSC-WA* (6)99 157416.0 (146266.5) 11622.1 (6413.2)
WA*
10 189241.9 (118754.7)
3151.0 (619.7)
Figures in parentheses are standard deviations.

Table 3: Performance of MSC-RTA* in maze.
Algorithm

Success
SearchSolution
Rate
Steps
Length
RTA*
100 7413.1 (10684.8) 363.5 (45.3)
MSC-RTA*(2)100 7852.9 (11200.9) 359.1 (43.7)
MSC-RTA*(3)100 7918.5 (11354.8) 358.5 (44.0)
MSC-RTA*(4)100 8005.1 (11508.4) 358.3 (43.7)
MSC-RTA*(5)100 8108.2 (11672.7) 358.1 (43.8)
MSC-RTA*(6)100 8104.4 (11689.5) 358.2 (43.9)
Figures in parentheses are standard deviations.

Table 4: Performance of MSC-RTA* in puzzle.
Algorithm

Success
SearchSolution
Rate
Steps
Length
RTA*
0
MSC-RTA* (2)100 155770.4 (126556.7) 44569.4 (29959.8)
MSC-RTA* (3)10093822.0 (60623.8) 23426.4 (14501.8)
MSC-RTA* (4)100 120639.8 (97361.6) 21230.7 (15697.6)
MSC-RTA* (5)100 181777.7 (182889.3) 24243.4 (31071.7)
MSC-RTA* (6)100 210496.5 (214838.1) 24511.4 (27474.1)
Figures in parentheses are standard deviations.

Figure 6: Maze and its heuristic values.
in the following case. Let us assume that the size ofSG(s1 ) is smaller than that of SG(s2 ). In this case,
if MSC aborts the search in SG(s1 ) and restarts it inSG(s2 ), the performance will su er. Moreover, if there
are more alternatives than s1 and s2 and their h values
look equally good, MSC may degrade its performancemore. This is a reason for performance degradation
when n is too large and for the MSC's superiority to
ASC.
From the above discussion, MSC shows better performance if the heuristic function is misleading (Condition 1) and if MSC can abort the search (Condition
2). Now, let us analyze whether these conditions are
satis ed with the maze and N-puzzle problems thatare used in the experimental performance analysis.
Figure 6 shows a maze. Its size is 6  6, the initialstate is (0,0), and the goal state is (5,5). The heuristic
value of a state is the Manhattan distance to the goalstate and it is written in the corresponding grid. These
heuristic values satisfy Condition 1 from the following
discussion. The initial state (0,0) has two child-states(0,1), which corresponds to s2 , and (1,0), which corresponds to s1 . Choosing (0,1) leads to the goal stateand is apparently a correct choice. However, both ofheuristic values are identical so this fact may cause awrong choice. However, Condition 2 is not satis ed.
This is because the h value of another candidate (0,1),
which corresponds to s2 , is not less than all of thestates in SG(s1 ) as shown in Figure 6. Hence, s2 is
not chosen from the commitment list regardless of nduring the search in SG(s1 ) so MSC is not expected
to be e ective in such maze problems.
Figure 7 shows a partial state space graph of a 15puzzle where the initial state is A and the goal stateis G. This problem satis es Condition 1. Namely, it isdicult to choose a right candidate because the heuris-

Figure 7: 15-puzzle and its partial state space graph.
tic values of the candidates B, C, D, and E, which
are the child-states of the initial state A, are identical(h = 10). In this case, choosing B is a wrong choice
as we discuss in the next subsection. In addition, thisN-puzzle also satis es Condition 2. That is because
the h values of child-states B, which corresponds to
s1 , are greater than that of C, which is corresponding to s2 . Hence, MSC eventually chooses s2 from thecommitment list, and returns to s2 from SG(s1 ), so it
is e ective in N-puzzle problems. On the other hand,
as shown in Figure 7, since N-puzzle has a numberof states with an identical h value, MSC, with largen, or ASC expands the search front too widely, anddegrades the performance or consume all the memory
before reaching a goal state.

6.2 Serializable Subgoals
MSC shows a dramatic performance improvement at
N-puzzles. As shown in Figure 5, the performancedi erence between SSC and MSC depends on the sizeof SG(s1 ) because SSC takes a long time for nishing
the search in SG(s1 ) but MSC can abort the search at
an early stage.
We here explain that the size of SG(s1 ) in N-puzzles
is large by introducing the concept of serializable subgoals [7],[11]. A problem has serializable subgoals i
the goal can be divided into a set of subgoals, andthere exists an ordering among the subgoals such thatthe subgoals can always be solved sequentially without ever violating a previously achieved subgoal in theorder [7]. For example, if we sort the bottom row of
the 15-puzzle as a subgoal, then we can always solve
the rest of the problem without disturbing the bottom row. Furthermore, if we sort the right column as
the next subgoal, the original 15-puzzle problem is reduced to an 8-puzzle. As in Figure 8, we can assign

a level to each of subgoals depending on the order ofachievement.
Hence, in the N-puzzle, it is better to choose an expansion state so that it does not destroy the subgoalthat have already been achieved. However, the heuristic value, which is the sum of the Manhattan distancesof misplaced tiles, does not re ect this property. For
example, in Figure 7, since the initial state has alreadyachieved the level-2 subgoal, choosing state B will destroy it. However, since the heuristic values of fourchild-states are identical, it is dicult to avoid the destruction. Once the algorithm destroys the subgoal,
it takes many steps to rebuild it, so in choosing state
B the performance is degraded. However, MSC canreturn to another candidate from the commitment list
so the wrong choice of B is not so fatal.
To support our discussion, we present how subgoals are destroyed in 24-puzzles in Table 5. In MSC
search algorithms, we de ne the level of achieved
subgoal as the highest one in the commitment list.
Precisely, the subgoal level at time T is de ned as
SLT = maxs COMMITMENTT SL(s) where SL(s) is thesubgoal level of state s. Please note this is not always
the same as the subgoal level of expanded state at time
T . Hence, the average steps to decrease subgoal levelis calculated from the whole search steps divided by
the number of events that decrease the subgoal level.
This table shows that more states with higher level
subgoal are preserved in the commitment list as n increases. Therefore, even if the algorithm chooses astate which destroys a subgoal temporally, it will easily choose another state which does not destroy thesubgoal. This e ect is strengthened by enlarging n.
2

Table 5: Subgoal destruction in 24-puzzle.
Algorithm
RTA*
MSC-RTA*(2)MSC-RTA*(3)MSC-RTA*(4)MSC-RTA*(5)MSC-RTA*(6)Average steps
to decrease
subgoal level
97.9
223.0
665.3
1327.31972.42719.3

7 Related Works
One method to decrease the risk of making wrong
choices is a method called cooperative search, in which
multiple problem solvers (agents) concurrently solve
an identical problem. Since there are multiple agents,

if at least one agent can make correct choices, a solution can be obtained in a reasonable amount oftime. Cooperative search methods have been applied
to constraint satisfaction problems [2, 4] and statespace search problems [6, 5].
One drawback to these cooperative search methods
is that if agents have to make critical choices repeatedly, those agents that made wrong choices early areunable to contribute to the ongoing search process.
[14] presents the multiagent real-time A* algorithm(MRTA*) with a GA-like selection mechanism. In thisalgorithm, a state-space search problem is solved concurrently by multiple agents. Each agent executes the
RTA* algorithm, and periodically reproduces o spring
stochastically based on its tness de ned by the heuristic value of its current state. Experimental evaluation
results show that this algorithm is very e ective in Npuzzles. Our work was inspired by [14], and we showthat much simpler algorithms can obtain similar results. While agents tend to do redundant actions, i.e.,
expanding identical states in MRTA*, our algorithms
in this paper avoid the redundance. For example, in[14], it is reported that the MRTA* algorithm withthe selection mechanism requires 35452.7 steps whenve agents3 solve the 48-puzzle problems concurrently(177263.5 steps in all). On the other hand, MSC-RTA*(where the length of the commitment list is 3) requires
only 93822.0 steps.
The beam search algorithm [1] is a classical method
for focusing/limiting the search e ort. In a beam
search, expanded nodes that are not included in thescope of the search attention are completely pruned.
As a result, the algorithm completeness cannot be
guaranteed so, for example, it can not solve manyof maze problems. In this paper, on the other hand,the completeness of the original algorithms (RTA* andWA*) is preserved.
A more modern method for focusing/limiting search
e orts is a family of Limited Discrepancy Search algorithms [3, 10]. These algorithms are based on adepth- rst search algorithm, and try to incrementallybroaden the search range by using heuristic information. These algorithms are suited to the problems witha known upper-bound of the search depth, such as constraint satisfaction problems.
One way for reducing the required memory size in
the A* algorithm is the SMA* algorithm [13], whichremoves unpromising nodes from the OPEN list. This
memory-reducing method and the idea of commitments introduced in this paper are not mutually exclusive, and can be used simultaneously.
3 This setting gives the best result both in the total steps andthe steps for each agent.

12 13 14 15711
12 13 14 1537
8 9 10 11
12 13 14 152 3
6 7
8 9 10 11
12 13 14 15

level 1level 2level 3level 43

Figure 8: Achievement of subgoals.
The recursive best- rst search (RBFS) algorithm [9]can run in linear space. However, as reported in [9],this algorithm does not work well when f(s) = h(s).
This is because the RBFS tends to explore all possible
paths to a given node, and the number of duplicate
nodes explodes as the search depth increases.

8 Conclusion
In this paper, we introduce the Multi-State Commitment method, which limits the search range, to two
semi-optimal solution search algorithms, WA* and
RTA*. We then evaluate their performance in mazeand N-puzzle problems and show a dramatic performance improvement in N-puzzle problems. We alsopresent required conditions for performance improvement that are satis ed in N-puzzles and the relation
to serializable subgoals.
The MSC method which uses a commitment list isa generic method to improve search eciency, so in
the future, we will apply this method to other kindsof algorithms and problems. In this paper, we do notdiscuss the optimal value of the parameter n. We guess
this depends on the character of problem and leave it
as an open problem. It is also interesting to provide adynamic method to adjust n during a search process.

References[1] Bisiani, R. 1992. Beam search. In Shapiro, S. C.,ed., Encyclopedia of Arti cial Intelligence. New
York: Wiley-Interscience Publication. 1467{1468.
[2] Clearwater, S. H.; Huberman, B. A.; and Hogg,
T. 1991. Cooperative solution of constraint satisfaction problems. Science 254:1181{1183.
[3] Harvey, W. D., and Ginsberg, M. L. 1995. Limited discrepancy search. In Proceedings of the
Fourteenth International Joint Conference on Arti cial Intelligence, 607{613.

[4] Hogg, T., and Williams, C. P. 1993. Solving thereally hard problems with cooperative search. In
Proceedings of the Eleventh National Conferenceon Arti cial Intelligence, 231{236.

[5] Kitamura, Y.; Teranishi, K.; and Tatsumi, S.
1996. Organizational strategies for multiagent
real-time search. In Proceedings of the Second International Conference on Multi-Agent Systems,
150{156.
[6] Knight, K. 1993. Are many reactive agents better
than a few deliberative ones? In Proceedings of
the Thirteenth International Joint Conference on
Arti cial Intelligence, 432{437.

[7] Korf, R. E. 1988. Search in AI: A Survey of
Recent Results. In Shrobe, H. E., ed., Exploring
Arti cial Intelligence . Morgan-Kaufmann.
[8] Korf，R. E. 1990. Real-time heuristic search.
Arti cial Intelligence, 42(2-3):189-211.
[9] Korf, R. E. 1993. Liner-space best- rst search.
Arti cial Intelligence, 62(1):41-78.
[10] Korf, R. E. 1996. Improved limited discrepancy
search. In Proceedings of the Thirteenth National
Conference on Arti cial Intelligence, 286{291.
[11] Newell, A. and Simon, H. A. 1972. Human Problem Solving. Prentice-Hall.
[12] Pearl, S. 1984. Heuristics: Intelligent
Search Strategies for Computer Problem Solving.
Addison-Wesley Publishing Company.
[13] Russel, S. 1992. Ecient memory-bounded searchmethod. In Proceedings of the Tenth European
Conference on Arti cial Intelligence, 1{5.
[14] Yokoo, M., and Kitamura, Y. 1996. Multiagent
real-time-a* with selection: Introducing competition in cooperative search. In Proceedings of theSecond International Conference on Multi-Agent
Systems, 409{416.