SeeA*: Efficient Exploration-Enhanced A* Search by Selective Sampling
Authors: Dengwei Zhao
Shikui Tu
Lei Xu
Venue: NeurIPS 2024 oral (2024)
Keywords: search algorithm
reinforcement learning
exploration
Primary area: reinforcement_learning
TL;DR: SeeA* is proposed to incorporate exploration into A* search by introducing an dynamic candidate set.

Abstract: Monte-Carlo tree search (MCTS) and reinforcement learning contributed crucially to the success of AlphaGo and AlphaZero, and A$^*$ is a tree search algorithm among the most well-known ones in the classical AI literature. MCTS and  A$^*$ both perform heuristic search and are mutually beneficial. Efforts have been made to the renaissance of A$^*$ from three possible aspects, two of which have been confirmed by studies in recent years, while the third is about the OPEN list that consists of open nodes of A$^*$ search, but still lacks deep investigation. This paper aims at the third, i.e., developing the Sampling-exploration enhanced A$^*$ (SeeA$^*$) search by constructing a dynamic subset of OPEN through a selective sampling process, such that the node with the best heuristic value in this subset instead of in the OPEN is expanded. Nodes with the best heuristic values in OPEN are most probably picked into this subset, but sometimes may not be included, which enables SeeA$^*$ to explore other promising branches. Three sampling techniques are presented for comparative investigations. Moreover, under the assumption about the distribution of prediction errors, we have theoretically shown the superior efficiency of SeeA$^*$ over A$^*$ search, particularly when the accuracy of the guiding heuristic function is insufficient. Experimental results on retrosynthetic planning in organic chemistry, logic synthesis in integrated circuit design, and the classical Sokoban game empirically demonstrate the efficiency of SeeA$^*$, in comparison with the state-of-the-art heuristic search algorithms.

SeeA*: : Efficient Exploration-Enhanced A Search by Selective Sampling
Dengwei Zhao', Shikui Tu'; Lei Xu
'Department of Computer Science and Engineering, Shanghai Jiao Tong University GGunngdong Institute of Intelligence Science and Technology {zdweec, tushikui, jei edw....d....m cn
Abstract
Monte-Carlo tree search (MCTS) and reinforcement learning contributed crucially the success of AlphaGo and AlphaZero, and A is tree search algorithm among the most well-known ones in the classical AI literature. MCTS and A both perform heuristic search and mutually beneficial. Efforts have been made to the renaissance of A from three possible aspects, two of which have been confirmed by studies in recent years, while the third about the OPEN list that consists of open nodes of A search, but still lacks deep investigation. This paper aims at the third, i.e., developing the search by constructing a dynamic subset of OPEN through a selective sampling process, such that the node with the best heuristic value in this subset instead of in the OPEN is expanded. Nodes with the best heuristic values in OPEN are most probably picked into this subset, but sometimes may be included, which enables SeeA to explore other promising branches. Three sampling techmiques are presented for comparative investigations. Moreover, under the assumption about the distribution of prediction errors, we have theoretically shown the superior efficiency of SeeA* over A' search, particularly when the accuracy of the guiding heuristic function is insufficient. Experimental results on retrosynthetic planning in organic chemistry, logic synthesis in integrated circuit design, and the classical Sokoban game empirically demonstrate the efficiency of SeeA*, in comparison with the state-of-the-ard heuristic search algorithms.
enhanced A (SeeA')
Introduction
In recent years, combining heuristic search algorithms with deep neural networks has demonstrated remarkable performance across wide range of practical applications, such board games [48] (50)
49 66), video games [46]
64
67 traveling salesman problem & [5], de novo drug design [42]. The search algorithm is slow
retrosynthetic planning 16
47 68 logic synthesis [9] and
reasoning process, and heuristic functions serve as counselors to narrow down search space [2]
Therefore, the effectiveness of search algorithms is significantly influenced by the quality of the guiding functions.
Monte-Caria tree search (MCTS) is widely- effective algorithm for combinatorial problems. However, if the backup value in MCTS provided by a heuristic estimator rather than actual rewards, the convergence to the true state value is not guaranteed, leading to compromised search performance. In single-agent problems such as combinatorial puzzles, neural-guided MCTS tends to have relatively long runtime and often generates solutions that are considerably longer than the shortest path []]
"Correspoddence authors are Shikui Tu and Lei Xu.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

A' search [26] is a best-first search algorithm that expands nodes with the minimum total path value at each step. The evaluation function f f() on node n is defined as the summation of g(z), the accumulated cost from the initial node no to and h(()) the expected cost from nt to the goal, i.e.,
f(n) = g(n) + h(n).
Notice that g(n) computes the cost from the known searching trajectory. whereas h(n) is a heuristic function to estimate the cost of the future path from n to the goal. In practice, it is usually difficult to obtain an accurate h(n). A search is guaranteed to find the optimal solution if li(n) is admissible, i.e. h(n)) never overestimates the real cost to the goal. However, due to its best-first expansion strategy, A has limited exploration capability. If (') deviates from the true cost function f (n) too much, A" search may become trapped in local optimal branches, and significant efforts are required to resume expansion within the optimal branch. Consequently, the computational efficiency of A* search is compromised in practical applications, even though the optimality of A might still hold under the guidance of f(n)..
MCTS and A both perform heuristic search. MCTS and reinforcement learning with the help of deep learning contributed crucially to the successes of AlphaGo and AlphaZero, which aroused the interest of comparing MCTS and A for possible mutual benefits. Deep learning is also able to contribute to the renaissance of A", three possible aspects are addressed with a family of possible improvements proposed under the name of Deep IA-search [6]] The first and also straightforward aspect is estimating (n) with the help of deep learning, which makes current studies on A including this paper into the era of learning aided A The second aspect is secking a better estimation of (() with the help of global or future information, featured by two typical mechanisms. One is lookahead or scouting before expanding the current node to collect future information to revise f(n) of the current node, which takes a erucial rule for the success of AlphaGo [48] and also used more than 30 years ago in Algorithm CNneim-A [62]. The other is path consistency, that is, f(n values on one optimal path should be identical, which has been further confirmed in recent studies [66] 67 68 This third aspect is about selecting nodes among the OPEN list that consists of open nodes of A It is an old tune even in the classical OPEN and WAIT according to a priori and a posteriori in a Bayesian evaluation [61. However, investigation is seldom made on what are effective and efficient ways for selecting among OPEN.
of A ", e.g., one suggestion is dividing OPEN into two sublists
In this paper, SeeA' search (short for Sampling-exploration enhanced A*) algorithm is proposed by incorporating exploration behavior into A search to target at the third aspect. The main contributions are summarized below
SeeA* search employs a selective sampling process to screen dynamic candidate subset D from the set O of open nodes that are awaiting expansion. The next expanding node is selected from D, and it may not be the node that has the best heuristic value in O and will be selected by A", enabling SeeA* to explore other promising branches. To reduce the excessive expansion of unnecessary nodes during exploration, only the candidate node with the best heuristic value is expanded. Three sampling strategies are introduced to strike a balance between exploitation and exploration. The search efficiency is improved especially when the guiding heuristic function is not accurate enough.
We theoretically prove that SeeA* has superior efficiency over A search when the heuristic value function deviates substantially from the true state value function. SeeA* achieves a reduced number of node expansions to identify the optimal path. This performance improvement becomes more pronounced as the complexity of the problems increases and the reliability of the guiding heuristics decreases.
Experiments are conducted on two real-world applications, i.e., the retrosynthetic planning problem in organic chemistry and the logic synthesis problem in integrated circuit design, well as the classical Sokoban game. SeeA* outperforms the state-of oh-the-art heuristic search algorithms in terms of the problem-solving success rate and solution quality while maintaining a low level of node expansions.
The source code is available httptt///igggiiiooo////////teeee _stta

---

2
Related work
MCTS [5 utilizes random sampling and tree-based search to efficiently explore search space. Upper Confidence bounds applied to Trees with predictor (PUCT) have been employed by AlphaZero 49]. achieving super-human performance in board games. A search is widely employed for solving optimization problems, such as route planning [54 [53], cubic and puzzle games [., robotics [ and so on, Many variants of A search have been proposed for performance improvement. Weighted A search (WA*) [18] biased the expanding policy towards states closer to the goal by
n arg min g(n) + Eh(n),
(2)
where E is a hyperparameter to adjust the weight of the heuristic estimation 4. WA* with iteratively decreasing weights is employed by the LAMA planner (27 44 achieving promising results in various domains including Sokoban. DeepCubeA [1 trained heuristic functions by reversing solution pathways from the goal state to guiding the search process of WA" Commonly. WA traded optimality for speed, and increasing E was assumed to result in faster searches. Additionally, the greedy search based on h values was considered the fastest search. However, empirical observations revealed that increasing slowed down the search in some domains. Greedy search is fast if and only if there is a strong correlation between the heuristic estimations and the true distance-to-go or if the heuristic is extremely accurate [55]. However, constructing reliable heuristic function for complicated problems is challenging attributed to the vast search space and the difficulties associated with sample collection in real-world applications. Poor generalization performance also remains pervasive issue across diverse practical domains, such as retrosynthetic planning. This paper sets out to develop efficient search algorithm designed to minimize the adverse effects of inaccurate predictions by heuristic functions.
There have been some preliminary studies on the integration of exploration into the A search. 8- --gredy node selection was incorporated into LAMA, suggesting that exploration can improve the coverage of search al algorithms even multiple enhancements were already employed [52]. Type-WA* WA [ augments WA" with type-based exploration [57] in the focal list [40]. The search space nodes are divided into 7'' distinct groups, and one of these groups is randomly chosen to determine the expanded node. Levin tree search (SevinTS) 38 combined penalization mechanism based on node depth encourage exploration for A' search. rolicy-guided heuristic search (PHS) [3) generalized LevinTS by introducing a heuristic factor, guided by both a value function and policy. When the guiding heuristics sufficiently accurate, the best-first search achieves optimal efficiency without the need for exploration. Insufficient exploration leads the search algorithm to be trapped in local optima guided by inaccurate heuristies. As the accuracy of the guiding heuristic diminishes, the importance of exploration becomes more pronounced in order to mitigate the potential misguidance.
Search algorithms have played crucial role in solving diverse real-world problems, such retrosyn- thetic planning and logic synthesis. Retrosynthetic planning aims to identify a feasible synthetic route using known available building block molecules for given target molecule. Considering that the synthesis of target molecules typically requires multiple steps and each step encompasses a substantial number of potential chemical reactions, retrosynthetic plamning is formulated as search problem to identify the optimal synthetic pathway. Both MCTS [28] 47 655 and A" search, such as Retro" (6) and its descendants 24
30 33 58) have demonstrated promising results in retrosynthetic planning. Logic synthesis (LS) is a crucial step in the design of integrated circuits, mapping the high-level logic circuit description into gate-level implementation. In recent years, reinforcement
learning algorithms [00 29, 34 41 (69 and search methods 9 37 have shown promising results in the field of LS. Besides, Sokoban is NP-hard (66] and PSPACE-complete [14] problem, which is a benchmark problem for evaluating the performance of artificial intelligence planning algorithms. Recently, combining reinforcement learning algorithms with search-based methods has demonstrated remarkable performance in effectively solving the Sokoban problem
19 20
31
3 Preliminaries and limitations on A search
Single-agent problems solved in this paper are formulated as Markov decision processes. Let AV represent the set of nodes in the search tree, where each node n E N corresponds to a state in the state space S. The set of n's children is represented as (H)) The root of the tree and the initial state are denoted as no and so respectively. At each interactive step, action a, A is
3

---

applied to the current state st, resulting in the subsequent state St+1 T(s 0e) and transition cost C++1 c(s,, az), where T is the state transition function obtain the following state 81+1 when taking action de at state St, and e is the cost function giveing the received cost when taking action de at state 8t-.
The search tree of A' contains two distinct types of nodes: closed nodes, which have already been expanded, and open nodes, which are waiting be expanded [26]. Let O and C denote the set of open nodes and closed nodes respectively. The search process of A' can be summarized as follows:
Step 1: Initialize no with so, and mark as open node by setting O {no}. C 0.
Step 2: Select the node n with the lowest total path cost f(n) from the open set O, i.e.
π arg go f'x')..
Step 3: If the node is the goal, terminate the search process successfully, Otherwise, expand the node n, and update C +- C (n). O t O u CH()) \ (n).
Step 4:
Repeat step 2 and 3 until O becomes empty, or exceeding the predetermined maximum runtime or the number of expanded nodes, terminating with failure.
A search always selects the node with the best heuristic value from the open set without exploration. When the heuristic function f can accurately estimate the true cost f", this best-first search is the most efficient. However, if the estimation by f is not accurate enough, the node with the minimum value may not correspond to the optimal one, which instead has the lowest f* value. The search process might be trapped in a local optimal branch, and substantial computational efforts are required resume expansion on the optimal branch, which diminishes the efficiency of the search algorithm. Considering an example in Figure [a), suppose the cost for each step (or edge) on the optimal path is 100, and on the non-optimal path is only 1. The true total path cost any node n is given by (n) = g(n) + h (n), where g(n) is given by adding the costs from the root to the node n, and the real future cost h" (n) is summation of all costs from n. to the end (or terminal state). Suppose the evaluation function f(n) g(n) + h(nz) by Equation [ is exact on the optimal path but underestimates the real cost otherwise. Specifically, define the heuristic function h(n) as follows:
h(n)= = h" (n). if on the optimal path 0, Otherwise
Then, h(n)) satisfies the admissible assumption it never overestimates the cost, and h(n) I h" (n) established for all nodes. Therefore, A* is guaranteed to find the optimal solution guided by h(n) in Equation 3 However, illustrated in Figure b), guided by the defined heuristic h, the nodes on the optimal path will not be expanded until all nodes on non-optimal branches with depths less than 200 have been expanded. The optimal solution is achieved within two steps under the guidance of f", and the search efficiency of A" search is largely compromised when f(n) is not accurate enough.
4 Method
SeeA* search is proposed on the basis of A' search by introducing a candidate set D of open nodes to provide exploration behavior. Three selective sampling strategies are presented for constructing the candidate set. Moreover, we present a theoretical analysis on the efficiency of SeeA*.
4.1 SeeA* " search algorithm
SeeA* employs the following two steps to replace the Step 2 in A* search. First, a selective strategy is employed sample set of candidate nodes DD from the opening set O. Then, the node with the lowest f-value from the candidate set D, instead of O, is chosen to be expanded in Step 3. The details of SeeA" are summarized in Algorithm in Appendix A
Step 2a: Sample a candidate subset D from O.
Step 2h: Select the node n with the lowest f-value from the candidate set D.
As illustrated in Figure (d), if the node with minimum f-value is not sampled into the candidate set D in Step 2a, the node selected to be expanded later not the same as the one by A" search, which activates exploration other branches. Step 26 excludes the unpromising nodes by the f-value.

---

Node expanded
Node not expunded
Goal node
Open
Transition cost
Optimal branch
Subuptimal brunch
Candidale set DC O "t (seelecce by SeeA")
(RRa)
200
13g
((m))
100
100
argmin (n)
argmin (m)
111,1
722,1
71111
22
(mag)
(c)
f (mn..)
(111)
200
100
f22.2
= 200
222
(mzze)
=2
Open set (sellccted by A')
1112
f (1ax)
72,2
10
Candidate set Dc 0
T22,000
22000
(M2200) 200
nj(selected by SenA")
ni argminteeo (n)
N2.30
(1210)) 10*
N2 argmin (1)
Exploration is enabled!
(b)
(d)
Figure I: An illustration of how SeeA* overcomes the A search's limitation. (a) An example of the search tree is guided by the true optimal value f f"n) g(n) + h (n). Values the edge denote the cost of each step. (b) On the same example, the A search is trapped in suboptimal branch misled by the unreliable heuristics, i.e., f(n g(n) h(n). (d) When the candidate set does not contain the node n with the best f value, nz will selected and explored, where nž * n
4.1.1 Uniform sampling strategy
Uniform sampling guarantees an equal selection probability for each node, thereby generating a representative subset that has the same distribution of the population. The procedure is given in Algorithm 2in in Appendix [A] If the desired number of candidate nodes, denoted as K, is greater than the number of open nodes, the open set O is used D. Otherwise, K nodes are randomly selected from the open nodes as 'D. It should be noted that SeeA* with uniform sampling is different from the e-Grredy method. The e-Greedy activates exploration with probability and then uniformly samples a node for expansion, which may expand low-quality nodes. Step 2a SeeA", uniform sampling very likely include at least one high-quality node with reasonably low f-value and the node will be selected to expand in Step 26. More discussions are referred to Appendix P
4.1.2 Clustering sampling strategy
In the uniform sampling strategy, each node is selected with equal probability. However, there is a non-negligible probability that all sampled nodes are of low quality, leading to the exclusion of nodes along the optimal expansion path from the candidate set D. Therefore, a clustering sampling strategy proposed, and partitions open nodes into multiple clusters and subsequently sampling nodes from each cluster, as illustrated in Figure 2 in Appendix B At least one node from each cluster is sampled compulsorily. Consequently, the probability of including nodes on the optimal branch is increased, thereby facilitating search efficiency. On the other hand, uniform sampling strategy is equivalent to assume that the nodes follow a Gaussian distribution, whereas clustering sampling strategy assumes that the nodes follow a Gaussian mixture distribution from multiple clusters, which provides more descriptive representation for sampling.
To reduce computational costs, competitive learning [1 is utilized for node clustering. After each node expansion, the incorporation of newly generated nodes into the set O resembles the process of online sample acquisition in competitive learning. A clustering process is conducted simultaneously with the search process. Offline clustering algorithms, such K-means Gaussian mixture model, require recalculating the clustering when incorporating new nodes, thereby imposing additional computational overhead. Each node is represented by a vector extracted by function fn- Nr cluster centers are randomly initialized as vectors with the same dimension of node embedding. During each expansion, the newly generated nodes are assigned to the cluster with the closest center separately, and the cluster center is updated by moving toward the position of the freshly added node. While preparing the candidate set D, nodes are sampled evenly from each cluster, and uniform sampling employed to select nodes from each cluster. Details displayed in Algorithm 3 & in Appendix A
5

---

4.1.3 UCT-like sampling strategy
In AlphaZero [49] PUCT achieved good balance between exploitation and exploration with promising results. In light of this, UCT-like sampling strategy proposed. Due to the absence of Monte Carlo simulations, estimated f values are employed to substitute the Q value in PUCT, which the average backup value obtained from multiple MCTS simulations. The depth of the node employed as the penalization for exploration 38 Each node is evaluated by
Vdmaz E(n) = f()) Co X I+ d(n)
where с₁ is an adjustable hyperparameter, d(n) is the depth of node πt, and dmaz is the maximum depth of the open nodes. Nodes with smaller d((n) are more likely be included in the candidate set for exploration. Despite potential errors in f value estimation, it remains viable node evaluation metric sample high-quality nodes, and the exploration term is beneficial in mitigating misleading of prediction errors. с to constitute the candidate set 2. The details are summarized in Algorithm in Appendix A
4.2 Efficiency of SeeA* * search
We further provide a theoretical analysis on the efficiency of SeeA", demonstrating that SeeA" is superior A when the guiding heuristic function does not estimate the true cost f accurately enough. was claimed in A search [26] that the f values all nodes on the optimal path are equal to the same cost pú and lower than the f* value of nodes outside the optimal path, which was assumed to be sampled from Gaussian distribution in (22] In this paper, the prediction error for f is assumed to follow uniform distribution. Here, Gaussian distribution is denoted as G(.,-) and uniform distribution is denoted ((.,)). .). Formally, an assumption is made as follows.
Assumption 4.1 For each node n on the optimal path, f(n) ~ U(1g a, uá o For nodes not on the optimal path, f(n) ~ (u(f((n) - o, (") o), and {f (n)} are independently and identically sampled from (p] oo?).
The M6 and uf are the expected total cost for optimal and non-optimal solutions, respectively. The inequality 16 < μff holds because the optimal path has a lower cost. The a represents the magnitude of the prediction error, and the o is constant the variance. Under Assumption 4.1
can derive:
Corollary 4.2 For node n on the optimal path and a node n' off the optimal path, the probability
Po P (f(n) S f(n))aa
(5)
decreases as the prediction error increases.
is worth noting that the establishment of Corollary 4.2 is not limited by the assumption of a uniform noise distribution in Assumption 4.1 When the noise follows Gaussian distribution, Corollary 4.2
still established. Refer to Appendix C for more detailed derivations.
Without loss of generality, assume the open set O contains No nodes, {ni, n2, ,NN,). and is the optimal node. The probability of A search expanding node nı is
Pa(a) = P = arg min
1(1))o) = II P(((n) S ((1))) = Po N.-1 n'EO
(6)
n'EO)(m))
SeeA* expands mı with probability
Ps(a) = P E D, arg min f(n')la P(n1 D n'EDi((m)
II
Po.
n'ED
If the uniform sampling strategy is used to select K candidates,
Ps(a) = N: Pe K-1
(8)
Based on Equation & when the prediction error a large, SeeA* * expands the optimal node with higher probability than A" search at each step, which is given by the following theorem.

---

Theorem 4.3 Ps(a) > PA(o) holds if and only if
Po < HN.),, where (NN)) (
K No
No
No K 1.
(N.) is monotonically increasing function with respect to No which is the size of the open set. With increasing branching factors and longer solution paths for more complex problems, No grows and H (No, K) monotonically increases with respect to No. Especially, we have
lim (NN)) =
(10)
In this situation, Inequality Pholds. SeeA* tends to demonstrate superior performance compared to A* in solving complex problems.
Notice that if the heuristic function / predicts the true cost f without error, it leads Pa 1 in Equation 5 Then, Equation D does not hold, and in this case, A search becomes more efficient than SeeA* However, learning an accurate heuristic function for complex real-world problems is quite challenging, and large prediction errors usually exist, which leads to small Pa and the establishment of Equation
| The number of candidate nodes K is key hyperparameter to balance the exploitation A and the exploration introduced by SeeA". (s(ar) in Equation 8 reaches its maximum value when K - logP.. Po. When Pa approaches 1, K will be the largest oc. In this situation, the candidate set is the same the open set, and SeeA* degenerates into best-first A'. For small pa. the optimal K* is the smallest value I and SeeA" becomes random sampling. An appropriate value of K should be selected according to the specific situation. According to Equation 7 (s( is related to both Po and P(n1 E D). Utilizing more efficient sampling algorithms than uniform sampling is also capable to enhance the performance of SceA*. The clustering sampling and UCT-like sampling aim to achieve a higher P(n1 E D) by constructing a more diverse candidate set, thereby enhancing the likelihood of expanding the optimal node.
For simplicity, suppose the probability of selecting the optimal node in a single expansion is P, and the probability for expanding the optimal node becomes - (1 - P)" after expansions. To achieve a probability level of Pmin for expanding the optimal node, we have
log P Pmiin]
(11)
log 1 P}
SeeA" is more efficient than A search as it requires fewer expansions to find the optimal solution. It is noted that Equation i derived on the uniform sampling strategy. For more effective sampling strategy with a higher probability P(n1 D). SeeA* will become more efficient as (a( increases.
Based on Theorem 4.3 and Equation 11
5 Experiments
Real-world problems are usually complicated, and the amount of available samples for training the heuristic functions is typically small. Two real-world applications, i.e., retrosynthetic planning in organic chemistry and logic synthesis in integrated circuit (IC) design, are considered to evaluate the effectiveness of the proposed method. Since the molecular structures have enormous diversity but in contrast the available experimental data are very limited, the heuristic function to estimate the synthe- sis cost in retrosynthetic planning suffers from noticeable overfitting problems [8] Furthermore, the vast chemical reaction space gives rise to a substantial number of branching factors in the search tree, leading rapid growth in the quantity of open nodes throughout the search process. Logic synthesis is another practical problem where it is challenging to train a reliable heuristic function to evaluate the solution's 's quality, due the immense diversity of circuit functionalities and variations in design methodologies. Therefore, the above two real-world problems are suitable benchmarks to verify the efficiency of SeeA* when the heuristic function is not accurate enough. In addition, Sokoban is a widely-used benchmark for combinatorial optimization solvers. It only permits a maximum of four legal actions at each step, and simulations can be leveraged to generate a substantial amount of data for training high-quality heuristic value estimators. Sokoban is included to verify the impact of an accurate heuristic function on the searching performance. All experiments are conducted using NVIDIA Tesla V V100 GPUs and an Intel(R) Xcon(R) Gold 6238R CPU.
7

---

5.1 Results on retrasynthetic planning
Chemical synthetic pathways are transformed into search trees following the literature 47 A state is a set of molecules that are able to synthesize the target molecule. The initial state contains only the target molecule. The edges in the search tree represent the chemical reactions that enable state transitions between the connected nodes. The retrosynthetic planning problem is solved if all molecules within a state are available building blocks. A single-step retrosynthetic prediction model is utilized as the policy model to generate potential chemical reactions yielding the input molecule. The 50 chemical reaction templates with the highest probabilities constitute the set of valid actions for the current state. A heuristic function is employed to estimate the synthesis cost of the molecule, given the available building blocks. Each molecule is encoded using a dinn-ndimesiooal Morgan Fingerprint vector [45] as the input for the heuristic functions. Both the single-step retrosynthetic prediction model and the cost estimator are provided by Retro"+ + [30] and used to guide the search algorithm. Details about the guiding heuristics are in Appendix D The last hidden layer's output of
the cost estimator is employed as the embedding representation of the input molecule.
Experiments are conducted on the widely-used USPTO benchmark, comprising 190 molecules [6]. Commercially available molecules in eMolecules are used as building blocks. Since the invocation of the single-step retrosynthetic prediction model contributes the majority of the computational cost, all search algorithms are limited to a maximum of 500 single-step model calls, or 10 minutes of real-time, following previous works 6 30). The outputs of the single-step model are cached to avoid duplicate computation when the same molecule is encountered again [36]. The size of the candidate set is set to K 50. In the clustering sampling, the parameter 1) is set to 0.15, and the number of clusters is 5. In the UCT-like sampling. the parameter Oo is set to 0.35. Additional pruning is not considered. Since the prior policy is already clipped minimum value of 0.001, Bayes mixing with uniform policy to avoid zero-probability is not used in LevinTS (38) and PHS [39].
The results on the USPTO benchmark are reported in Table Due to the exploration induced by selective sampling, the three SeeA* variants achieve superior performance in terms of the percentage of solved molecules and the average solution length while utilizing minimal wall-clock runtime. Among the three sampling strategies, the UCT-like sampling strategy achieves the best balance between exploration and exploitation. As in the literature [47). predicting the synthetic cost of molecules is challenging, and the cost estimator is not accurate with a non-negligible prediction error a. Then, it is expected and consistent with Theorem 4.3 that best-first search algorithms, including WA" and PHS, are less efficient because they excessively rely on the values of the heuristic function. and generates solutions with longer lengths, which is consistent with the findings in the resolution of combinatorial puzzles []]. The e-Greedy node selection [52] achieves a success rate of 92.11%, surpassing the performance of A* search and demonstrating the practical benefits of introducing exploration when the reliability of guidance heuristics is compromised.
MCTS requires more node expansions for problem-solvine
Six additional datasets are collected from the literature for further comparisons. These datasets comprise 4719 molecules, much more than the USPTO dataset. Details of the datasets referred to the Appendix [E, According to the results in Table 3 4 in Appendix G SeeA* maintains its superiority over other search algorithms, and "CeustCluster has the highest mean success rate of 63.56%. The clustering sampling and UCT-like sampling are better than uniform sampling in terms of the solved rate and the route length, indicating that the utilization of a superior sampling strategy is beneficial for the performance of SeeA*.
5.2 Results on logic synthesis
For the logic synthesis problem, a Verilog- hardware design is first converted into an and- inverter-graph (AIG) representation, and then the AIG is optimized have the lowest area-delay product (ADP) through a sequence of combinatorial because the sequence is constructed by selecting transformations one-by-one in order from a set. Following the literature, here the set is formed by seven legal transformations. and the sequence length is fixed at 10. The resyn2 transformation sequence used as a baseline for comparison
preserving transformations. The optimization
comparisons 9 10 37). More details about logic synthesis are in Appendix H During the search
hatt:://doonloo www.eaaa....lleeeeeeeeeeeemeeeee emolecules. httm/ffree20223320 12-01/
"Red entries indicate the top rank, while blue entries signify the second position. Table 2 remains consistent.
8

---

Table 1: Test results on the USPTO benchmark for retrosynthetic planning problem.
Algorithm
Solved (%) 1
Length |
Expansions +
Avg time (in seconds)
Retro" 16
86.84
9.71
157.11
110.57
Retro 30
91.05
8.74
100.15
61.24
MCTS MCTS(Cpuct Cpuct 4.0)
89.47
8.23
122.97
87.86
A search
88.42
9.27
92.45
96.07
WA (E 1.5)
84.21
10.16
106.97
120.69
LevinTSS 38
96.84
7.45
57.11
39.77
PHS
39
87.37
10.19
93.38
108.85
e-Greedy (c=0.1)
92.11
43.78
89.14
76.59
SeeA Seen-(Uni
96.84
7.34
72.08
49.77
SeeA" (Cluster)
98.42
6.48
79.75
37.98
SeeA" (UCC)
98.95
6.36
62.07
32.38
process, the immediate reward is set to be O, and the reward of the terminal step is the final AIG's ADP reduction rate against the baseline resyn2. The ADP score approximately computed by ABC
4. A heuristic function is employed predict the accumulated reward of sequence when only a front part of the sequence is available as input the search process. This function serves as a guiding heuristic for the search algorithms. Following ABC-RL [9], the training dataset consists of 15 circuits, while the test dataset comprises 12 MCNC circuits denoted as {C1 ~ C12) [63] (See Appendix [ for more details.). The architecture of the heuristic function, the training and test details
are referred to Appendix WA" is equivalent to A search because = O in Equation 2
The results the MCNC benchmark are presented in Table A All three SeeA* variants outper- form the existing methods terms of the mean ADP reduction rates against the baseline resyn2. SeeA* (CluseC))) achieves the highest ADP reduction (i.e., 23.5%), obviously surpassing the state- of-the-art ABC-RL's 20.9%. Guided by the same heuristic, SeeA "eeA*(CCrn (Cluster) outperforms search in 11 out of the 12 testing circuits. As illustrated by example of the search process in Appendix K the nodes expanded by A tend to concentrate on a specific branch, whereas MCTS expands across multiple branches excessively due to its enforced exploration. SeeA* achieves good balance between A search and MCTS, ensuring that irrelevant branches are not unduly explored.
A"
Table 2: The ADP reduction (%) rates against the resyn2 baseline on the MCNC testing datasets.
Algorithm
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
Mean
DRiLLS 29
18.9
6.7
8.0
13.0
38.4
19.1
5.4
18.0
14.3
18.6
6.6
11.0
14.8
Online-RI RL
69
20.6
6.6
8,1
13.5
39.4
21.0
5.0
17.9
16.2
20.2
4.7
11.4
15.4
SA+Pred.
10
17.6
17.0
15.6
13.0
46.5
18.2
8.5
23.6
19.9
17.6
10.0
20.3
19.0
MCTS [37
17.1
15.9
13.1
13.0
46.9
14.9
6.5
23.2
17.7
20.5
13.1
19.7
18.5
ABC-RL.(9
19.9
12.1
21.6
20.9
A' search
18.3
16.6
19.7
15.7
43.6
15.2
13.3
25,5
19.4
20.8
7.5
18.8
19.5
5-Greodyls = 0.1) 52
18.3
16.6
20.9
15.6
45.8
19.9
11.5
24.5
19.4
20.8
15.3
18.7
20.6
PV-MCTS
17.3
20.0
27.9
20.1
27.3
20.7
13.5
24.7
14.3
14.1
14.7
20.0
19.5
PHS 30
21.4
11.7
10.2
12.0
20.8
15.9
SeeA (Umiform)
21.9
18.7
21.9
16.5
37.2
13.8
12.3
25,5
21.5
24.1
21.5
24.0
21.6
SeeA (Cluster)
23.2
20.8
22.7
16.2
45.9
22.6
13.4
24.8
22.4
24.2
20.3
25.1
23.5
SeeA (UUT)
20.2
16.6
25.3
17.8
46.4
25.5
10.6
24.4
18.0
28.7
17.5
23.6
22.5
5.3 Results on Sokoban and path finding
The first 50000 training problems and the 1000 test problems are collected from Boxoban 233 They are utilized to train cost estimator and evaluate the search algorithms, respectively. More training details are provided Appendix L During testing, the search process is terminated with failure if the running time exceeds 10 minutes. SeeA" has successfully solved all 1000 test Sokoban cases. Notably, the solutions generated by SeeA* exhibit not only shorter lengths compared to other search algorithms such A search, WA LevinTS, and PHS but also shorter lengths than the
'The MCTS in 377 did not utilize any guiding heuristics. and fast rollout was employed for node evaluation. PV-MCTS and PHS were guided by the policy from ABC-RL and the value function trained in this paper.

---

State-of-the-ar DeepCubeA [ algorithm. Detailed results are summarized in Appendix M To illustrate the effectiveness of SeeA" on problems where accurate heuristics could exist but the guiding path finding are conducted. A' and SeeA* exhibit similar
heuristic used is unreliable, experiments
performance when the guidance heuristic reliable enough. However, SeeA" demonstrates significant advantages over A when the heuristic is unreliable. More details are available in Appendix N
5.4 The impact of the hyperparameters on the performance
The effects of three hyperparameters in SeeA* " are empirically investigated below, i.e., the number of candidate nodes K, the number of clusters Ne. and the adjustable weight c& in Equation 4 Experiments are conducted on the USPTO benchmark for the retrosynthesis planning problem. The number K is critical parameter controlling the extent of exploration of SeeA". When K = 1, the node to be expanded is solely determined by the selective sampling strategy, where the heuristic function has no impact the selection. When K' is too large, all opening nodes will be finally chosen as candidates because every node has a positive chance to be selected by the sampling strategy. In this case, SeeA* degenerates back to A which highly depends on the heuristic function. When K is at an appropriate range, the sampling scheme endows SeeA with helpful exploratory capability. is observed from Figure 11 in Appendix O that wide range of K enables SeeA* obtain superior performance. For the extreme cases, SeeA "KK = 1) has the lowest success rate and longest solution length, and the performance of SeeA
oo), which is equivalent A", is also discounted.
According to the results in Figure 12 in Appendix O the performance of the clustering sampling strategy is generally very robust against the choices of No. An inadequate number of clusters makes it towards uniform sampling by ignoring the differences among the nodes, while an excessive cluster number will distract the sampling process by noise in the node representation learning. The hyperparameter с₁ controls the balance between exploration and exploitation in the UCT-like sampling strategy. A large G favors exploration during the selection of candidate nodes. From Figure [3] in Appendix O either too large or too small c are detrimental to the efficiency of SeeA", and the UCT-like sampling strategy achieves excellent results when o9 is in the range of (0.15, 0.4].
6 Conclusion
In this paper, the SeeA' search is proposed to enhance the exploration behavior of the A search by selecting expanded nodes from the sampled candidate nodes, rather than the entire set of open nodes. node that is evaluated not to have the best estimated heuristic value may be selected and explored, thereby jumping out of the local optimum induced by inaccuracies in the heuristic function. Three sampling strategies are presented in the paper. Furthermore, we have theoretically established that SecA" is more efficient than A search when the estimation of heuristic functions is not accurate enough. Experiments on two diverse real-world applications in chemistry and eircuit design and one puzzle-solving game demonstrate the efficiency of SeeA".
If the model exhibits precise state evaluation, the incorporation of exploration into A search becomes redundant. However, in practical applications, where problems tend to be intricate or lack sufficient training data, obtaining accurately predictive heuristic functions challenging. As suggested in Equation [ in addition to reducing the prediction error a, the probability of expanding the optimal nodes is also improved by using smaller number of candidate nodes K include the optimal node in the candidate set with a greater likelihood P(n1 E D). Screening candidate nodes reduces the search space. thereby enhancing search efficiency. Investigations on more effective sampling strategies will be conducted in future work. SecA" will contribute to solving practical problems with limited samples. However, this work is still in the nascent stages without further applications related to people's 's daily lives currently, and thus there are no immediate ethical or harmful social impacts.
Acknowledgement
This work was supported by the National Natural Science Foundation of China (grants No. 62172273) and the Shanghai Municipal Science and Technology Major Project, China (Grant No. 2021SHZDZX0102).
10

---

References
[1] Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356-363. 2019.
[2] Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. Advances in neural information processing systems, 30, 2017.
[3 Mohak Bhardwaj. Sanjiban Choudhury, and Sebastian Scherer. Learning heuristic search via imitation. In Conference on Robot Learning, pages 27 271- PMLR, 2017.
[4] Robert Brayton and Alan Mishchenko. Abe: An academic industrial-strenghe verification tool. In Computer Aided Verification: 22nd International Conference, CAV 2010, Edinburgh, UK, July 15-19, 2010. Proceedings 22, pages 24-40. Springer, 2010.
[5] Hyeong Soo Chang, Michael Fu, Jiaqiao Hu, and Steven Mareus. An adaptive sampling algorithm for solving markov decision processes. Operations Research, 53(1): 2005.
[6] Binghong Chen, Chengtao Li, Hanjun Dai, and Le Song. Retro*: learning retrosynthetic planning with neural guided a search. In International Conference on Machine Learning, pages 1608-1616. PMLR, 2020.
[7] Tiejun Cheng, Yuan Zhao, Xun Li, Fu Lin, Yong Xu, Xinglong Zhang, Yan Li. Renxiao Wang, and Luhua Lai. Computation of octanol- water partition coefficients by guiding additive model with knowledge. Journal of chemical information and modeling, 47(6) 2007.
[8) Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tiemey, and Youngjune Gwon. Simulation-guicn beam search for neural combinatorial optimization. Advances Neural Information Processing Systems, 35:8760-8772, 2022.
[9] Animesh Basak Chowdhury, Marco Romanelli, Benjamin Tan, Ramesh Karri, and Siddharth Garg. Retrieval-guide reinforcement learning for boolean circuit minimization. In The Twelfth International Conference on Learning Representations, 2023.
[10] Animesh Basak Chowdhury, Benjamin Tan, Ryan Carey, Tushit Jain, Ramesh Karri, and Siddharth Garg. Bulls-eye: Active few-shot learning guided logic synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.
[11] Eldan Cohen, Richard Anthony Valenzano, and Sheila A Mcllraith. Type-wa*: Using explo- ration in bounded suboptimal planning. In IJCAL, pages 4047-4053, 2021.
[12] Connor W Coley, William H Green, and Klavs F Jensen. Rdchiral: rdkit wrapper for handling stereochemistry in retrosynthetic template extraction and application. Journal of chemical information and modeling, 59(6))2529-2537, 2019.
[13] Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pages 72-83. Springer, 2006.
[14] Joseph Culberson. Sokoban is pspace-complete. 1997.
[15] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1 fts/1880.00803, 2018.
[16] Dorit Dor and Uri Zwick. Sokoban and other motion planning problems. Computational Geometry, 13(4):215 1999.
[17] František Duchoñ, Andrej Babinec, Martin Kajan, Peter Beño, Martin Florck, Tomáš Fico, and Ladislav Jurišica. Path planning with modified a star algorithm for a mobile robot. Procedia engineering, 96:59-69, 2014.
[18) Rüdiger Fbendt and Rolf Drechsler. Weighted search unifying view and application, Artificial Intelligence, 173(14):1310-1342 2009.

---

[19] Dieqiao Feng, Carla P Gomes, and Bart Selman. A novel automated curriculum strategy to solve hard sokoban planning instances. Advances in Neural Information Processing Systems, 33:3141-3152, 2020.
[20] Dieqiao Feng, Carla P Gomes, and Bart Selman. Solving hard ai planning instances using curriculum-driven deep reinforcement learning. arXiv preprint urXiv:2006.02689, 2020.
[21] Kaitlyn M Gayvert, Neel S Madhukar, and Olivier Elemento. A data-driven approach to predicting successes and failures of clinical trials. Cell chemical biology. 23(10):1294 1301, 2016.
[22] Edward Groshev, Maxwell Goldstein, Aviv Tamar, Siddharth Srivastava, and Pieter Abbeel. Learning generalized reactive policies using deep neural networks. In Proceedings of the International Conference on Aulomated Planning and Scheduling, volume 28, pages 408-416, 2018.
[23] Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sebastien Racaniere, Theophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, et al. An investigation of model-free planning: boxoban levels, 2018.
[24] Peng Han, Peilin Zhao, Chan Lu, Junzhou Huang, Jiaxiang Wu, Shuo Shang, Bin Yao, and Xian- gliang Zhang. Gnn-retro: Retrosynthetic planning with graph neural networks. In I Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4014-4021, 2022.
[25] Katja Hansen, Sebastian Mika, Timon Schroeter, Andreas Sutter, Antonius Ter Laak, Thomas Steger- Hartmann,, Nikolaus Heinrich, and Glaus-Robert Muller. Benchmark data set for in silico prediction of ames mutagenicity. Journal of chemical information and modeling, 49(9):0077- 2081, 2009.
[26] Peter Hart, Nils J Nilsson, and Bertram Raphael. formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-100 1968.
[27] Malte Helmert. The fast downward planning system. Journal of Artificial Intelligence Research, 26:191-246 2006.
[28] Siqi Hong. Hankz Hankui Zhuo, Kebing Jin, Guang Shao, and Zhanwen Zhou. Retrosynthetic planning with seariencee-uudee monte carlo tree search. Communications Chemistry, 6(1): 2023.
[29] Abdelrahman Hosny, Soheil Hashemi, Mohamed Shalan, and Sherief Reda. Drills: Deep rein- forcement learning for logic synthesis. In 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC), pages 581 181-.86. IEEE, 2020.
[30] Junsu Kim, Sungsoo Ahn, Hankook Lee, and Jinwoo Shin. Self-improved retrosynthetic planning. In International Conference on Machine Learning, pages 5486 5495. PMLR, 2021.
[31] Peter Kissmann and Stefan Edelkamp. Improving cost-optimal domain-independent symbolic planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, pages 992 997, 2011.
[32] Greg Landrum. RDKit: Open-source cheminformatics software. http://www..rkki.org.. Accessed Nov 20, 2016.
[33] Guoqing Liu, Di Xue, Shufang Xie, Yingce Xia, Austin Tripp, Krzysztof Maziarz, Marwin Segler. Tao Qin, Zongzhang Zhang, and Tie- Yan Liu. Retrosynthetic planning with dual value networks. In Proceedings of the 40th International Conference on Machine Learning, ICML/23. Jogg 2023.
[34] Chenyang Lv, Ziling Wei, Weikang Qian, Junjie Ye, Chang Feng, and Zhezhi He. Gpt-Is: Generative pre-trained transformer with offline reinforcement learning for logic synthesis. In 2023 IEEE 4 41st International Conference on Computer Design (ICCD), pages 320-326. IEEF, 2023.
12

---

[35] Ines Filipa Martins, Ana L Teixeira, Luis Pinheiro, and Andre O Falcao. A bayesian approach in silico blood-brain barrier penetration modeling. Journal of chemical information and modeling, 52(6): 1697, 2012.
[36] Krzysztof Maziarz, Austin Tripp, Guoqing Liu, Megan Stanley, Shufang Xie, Piotr Gaiński, Philipp Seidl, and Marwin Segler. Re-evaluating retrosynthesis algorithms with syntheseus. arXiv preprint arXiv:2310. 19796, 2023.
[37] Walter Lau Neto, Yingjie Li, Beere--Emannee Gaillardon, and Cunxi Yu. Flowtune: End-to- end automatic logic optimization exploration via Nomain-speciffe multi-armet bandit. IEEE Transactions on Computer- Design of Integrated Circuits and Systems, 2022.
[38] Laurent Orseau, Levi Lelis, Tor Lattimore, and Théophane Weber. Single-agent policy tree search with guarantees. Advances in Neural Information Processing Systems, 31, 2018.
[39] Laurent Orseau and Levi HS Lelis. Volicy-guided heuristic search with guarantees. In Pro- ceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 12382 12390, 2021.
[40] Judea Pearl and Jin H Kim. Studies in semi-admissible heuristics. IEEE transactions on pattern analysis and machine intelligence, (4):392-399, 1982.
[41] Yasasvi V Peruvemba, Shubham Rai, Kapil Ahuja, and Akash Kumar. Rl-guided runtime- constrained heuristic exploration for logic synthesis. In 2021 IEEE/ACM International Confer- ence On Computer Aided Design (ICCAD), pages 1-9. IEEE, 2021.
[42] Hao Qian, Cheng Lin, Dengwei Zhao, Shikui Tu, and Lei Xu. Alphadrug: protein target specific de novo molecular generation. PNAS nexus, 1(4):pgac227, 2022.
[43] Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adrià Puigdomènech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, et al. Imagination- imagination-augmeented agents for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
[44] Silvia Richter and Matthias Westphal. The lama planner: Guiding cost-based anytime planning with landmarks. Journal of Artificial Intelligence Research, 39:127-177, 2010.
[45] David Rogers and Mathew Hahn. Extendedd-ooneecte fingerprints. Journal of chemical information and modeling, 50(5):742-754, 2010.
[46] Julian Schritwieserr, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604 609, 2020.
[47] Marwin HS Segler, Mike Preuss, and Mark Waller. Planning chemical syntheses with deep neural networks and symbolic ai. Nature, 555(7698):604-610, 2018.
[48] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484-88) 2016.
[49] David Silver, Thomas Hubert. Julian Schrittwesser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre. Dharshan Kumaran, Thore Graepel. et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 11044419)::11011111 2018.
[50] David Silver, Julian Schrittweeeer, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 359, 2017.
[51] Toshio Uchiyama and Michael Arbib. An algorithm for competitive learning in clustering problems. Pattern Recognition, 17110):1415-1422 1994.
13

---

[52] Richard Valenzano, Nathan Sturtevant, Jonathan Schaeffer, and Fan Xie. A comparison of knowledge-band based gbfs enhancements and knowledge-frie free exploration. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 24, pages 375-379, 2014.
[53] Jiankun Wang, Wenzheng Chi, Chenming Li, Chaoqun Wang, and Max Q-H Meng. Neural nt:: Learning-bast -based optimal path planning. IEEE Transactions on Automation Science and Engineering, 17(4): 2020.
[54] Jingyuan Wang, Ning Wu, Wayne Xin Zhao, Fanzhang Peng, and Xin Lin. Empowering a* search algorithms with neural networks for personalized route recommendation. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 539-547, 2019.
[55] Christopher Wilt and Wheeler Ruml. When does weighted a fail? In Proceedings of the International Symposium on Combinatorial Search, volume 3, pages 137-144, 2012.
[56] Kedi Wu and Guo-Wei Wei. Quantitative toxicity prediction using topology based multitask deep neural networks. Journal of chemical information and modeling, 58(2):520-531, 2018.
[57] Fan Xie, Martin Müller, Robert Holte, and Tatsuya Imai. Type-baser exploration with multiple search queues for satisficing planning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 28, 2014.
[58] Shufang Xie, Rui Yan, Peng Han, Yingce Xia, Lijun Wu, Chenjuan Guo, Bin Yang, and Tao Qin. Retrograph: Retrosynthetic planning with graph search. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2120-2129, 2022.
[59] Zhihao Xing and Shikui Tu. A graph neural network assisted monte carlo tree search approach 2020.
to traveling salesman problem. IEEE Access, 8:108418-
[60] Guoli Xiong, Zhenxing Wu, Jiacai Yi, Li Fu, Zhijiang Yang, Changyu Hsieh, Mingzhu Yin, Xiangxiang Zeng, Chengkun Wu, Aiping Lu, et al. Admetlab 2.0: an integrated online platform for accurate and comprehensive predictions of admet properties. Nucleic Acids Research, 49(W1):W5-W114 2021.
[61] Lei Xu. Deep bidirectional intelligence: Alphazero, deep ia-search, deep ia-infer, and tpc causal learning. Applied Informatics, 5(1), 2018.
[62] Lei Xu, Pingfan Yan, and Tong Chang. Algorithm enneim-a and its mean complexity. In Proc. of 2nd international conference on computers and applications. IEEE Press, Beijing, pages 494-499, 1987.
[63] Saeyang Yang. Logic synthesis and optimization benchmarks user guide: version 3.0, Citeseer, 1991.
[64] Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data. Advances in Neural Information Processing Systems, 34:25476-25488, 2021.
[65] Yemin Yu, Ying Wei, Kun Kuang, Zhengxing Huang, Huaxiu Yao, and Fei Wu. Grasp: Navigating retrosynthetic planning with goal-driven policy. Advances in Neural Information Processing Systems, 35: 12257727-,, 2022.
[66] Dengwei Zhao, Shikui Tu, and Lei Xu. Efficient learning for alphazero via path consistency. In International Conference on Machine Learning, pages 26971-26998 PMLR, 2022.
[67] Dengwei Zhao, Shikui Tu, and Lei Xu. Generalized weighted path consistency for mastering atari games. In seirty- Conference on Neural Information Processing Systems, 2023.
[68] Dengwei Zhao, Shikui Tu, and Lei Xu. Efficient retrosynthetic planning with mets exploration enhanced * search. Communications Chemistry, 7(1):52, 2024.
[69] Keren Zhu, Mingjie Liu, Hao Chen, Zheng Zhao, and David Z. Pan. Exploring logic optimiza- tions with reinforcement learning and graph convolutional network. Proceedings of the 2020 ACM/IEEE Workshop on Machine Learning for CAD, pages 145-150, 2020.
14

---

A Pseudocodes for SeeA* and its sampling strategies
In this section, pseudocode for the SeeA* search algorithm, and three sampling strategies: uniform sampling strategy, clustering sampling strategy, and UCT-like sampling strategy, are given. Algo- rithm Sahmmpprovitee provides comprehensive summary the computational process of SceA*. The algorithm begins by initializing the Open set Owith the initial node no. In each step, candidate set ' is obtained using the sampling strategy P. The node with the minimum value from the candidate set is selected to be expanded. If the algorithm reaches goal state, it successfully finds a solution and terminates. Otherwise, the expanded node moved the Closed set and its child nodes are added to the Open set O. This process is repeated until the O becomes empty.
The uniform sampling strategy is presented in Algorithm 2 If the size of the open set |O| does not exceed the required number of candidate nodes to be sampled, all nodes in the open set are considered as candidate nodes. However, if the size exceeds the required number, K nodes uniformly sampled from the open set to serve as candidate nodes.
Algorithm I: SeeA* search algorithm
Input: root node fg. sampling strategy F, the number of candidate nodes K, the maximum number of expansions Tmax and heuristic evaluation function f. Initialize C + 0, + {no}. and t <-
repeat
Prepare candidate set D = FOO,K) arg min f(n). if the goal node then return else
C C- CU,U ( OUCH(()) (n). end if
+ t+1
until O is empty or t 2 Tmaa return False
Algorithm 2: Uniform sampling strategy
Input: open O, the number of candidate nodes K. if [ < K then
return O
else
D c Uniformly sample K nodes from O
return D
end
Algorithm 3: Competitive clustering sampling strategy
Input: clusters S = {Si S ... S% }. the number of candidate nodes K.
Initialize D <- 9
Ke
K
for S E do
if [s:] < Kg then
D; + S
else
D; + Uniformly sample K, nodes from SÇ
end if
D t DUD;
end for return
The clustering sampling strategy summarized Algorithm 3 The open nodes are divided into No clusters, and an equal number of candidate nodes sampled from each cluster. To sample K
15

---

candidate nodes, each cluster requires sampling Kg = [ K nodes. For each cluster, if the number [S=] of open nodes within this cluster does not exceed Ke, all nodes selected candidate nodes, Otherwise, Kg nodes are uniformly sampled as candidate nodes. To reduce computational overhead, competitive learning employed for clustering, enabling avoidance of the need for re-clustering when new open nodes are added after each expansion. The algorithm for this competitive clustering process is displayed in Algorithm[5] N, clustering centers initialized randomly. When new node added to the open set, it is assigned to the cluster whose center is closest to it, and the coordinates of that cluster center updated by moving toward the position of the newly added node.
UCT-like sampling strategy is provided in Algorithm respectively. Each node n is evaluated by a statistic E(n) in Equation 4 which can achieve balance between exploitation and exploration. The value of the node is used to evaluate the quality and the depth d(n) used to encourage exploration. If the size of the open set |O| does not exceed the required number of candidate nodes to be sampled, all nodes in the open set are considered as candidate nodes. Otherwise, the nodes with the smallest E values selected as the candidate nodes.
Algorithm 4: UCT-like sampling strategy
Input: open set O, the number of candidate nodes K, hyperparameter if [ < K then
return O else
dmaz + max d(n)
for E O do
Calculate E(n) with Equation end for
D - [n| E(n) is the K smallest values in O}
return
end if
Algorithm 5: Node expanding for competitive clustering
Input: clusters 5 (Si. S5,... .... _ and their centers W (wf, wg, ". , .. expanded node n. feature extraction function fh. and weight !7.
for n CH((n) do
w <- [n(
f- arg min | - will
SJ - Sj (n)
wF + wf + x (w wf)
end for
return S We
B An example of the clustering sampling strategy
As shown in Figure 2 (a), the sampled nodes exhibit uniform distribution overall, resulting in proportional relationship between the number of sampled nodes within each cluster and the total number of nodes within each class. Clusters with fewer nodes are highly susceptible to the occurrence of no nodes being sampled as candidate nodes under limited sampling size. Therefore, this sampling strategy cannot effectively explore the various potential expansion directions. As depicted in Figure (b), at least one node from each cluster is sampled compulsorily, Consequently, the probability of including nodes on the optimal branch is increased, thereby facilitating search efficiency.
C Monotonicity of po
Po is the probability of P (f(m) < (n')), ), in which n is the node on the optimal path and n' is the node on the non-optimal path. According to Assumption 4.1
P((())a)) ~ u41g a,10 +
(12)
P(f(r())ps (n(((()) f'n)))
(13)
16

---

Selected open node
Unselected open node
Optimal node cluster
(a)
(b)
Figure 2: Set of selected candidate nodes obtained by (a) uniform sampling strategy; (b) clustering
sampling strategy.
f(n) ~ ((n')9(uf,.ol G(1/.02).m4 > Hb
(14)
If m0 ff())
(((())((()))))) 2 vá + 20,00 =
(15)
If p1 o ftr)) to:
p()(n) ((W)1))))))) s uó - -2,00) =0
(16)
p40 20 S f(n)n) po:
:((')+ (((n')t df(n))d(())
Pff(n) & (n)))
(17)
u6-0
20 s(m))
20
1 ('('')t ((()))=--()))())))
(f'(n') - 1b + 20
4 116-0
802
If nd fn') 1/6 20:
"(6'-0 (nn)==o 1
P(f(n) < f(1'))
(n))d((n)
Ju6
20
('W)-o
20
Nóto
((')to
1
(f
(18)
|(w))-
20
s(m)
20
(n')
("")+
('()-- 20 df(n'ddf(n)
-6--0
20
(n(n') + (nnn) + +o)(f(nn') 1/6 o))
402
(n() - -16) ('(n') - 1r
(19)
402
17

---

[ (aana 20 s(m)
plóto 1 ('(17t
1
(n()d()(())
20
(p(m))-13) 2
((n') :o0))o--(00 [(n) ds(n)
1
(20)
402
2
80
(M(n') - 11
((0)(()))) (n(n() - -16
1
+
20
2
802
-1 (f(n') m²6 20
(21)
807
In summary:
1,
fn 2 Hb +2
2
20 (1")n)) - 116 -20)
mb S (nl) < <Hd +2
(ff(n) $ (1)))
80
(22)
(f'n'') - HÓ + +20
2
11 20 S (n') < mg
80
0, f'n') S m/6 -2
We have that:
{ s f(r))o) / (1)))
(23)
f((() 0(
(24)
then we want to prove that (([(n) S s(n')) decreases with a. Let m(s'(n')oo) = (f((m) s ((r)))(("")) we first prove that m(f"(n)))) centrally symmetric about (M/) } by proving that (f (n")))) 1 (2nó (n')lo)
If fn!) 2 mg + 20:
m (((()')) =1
(25)
2/16 f'(n') s sn6 -22 20
(26)
m (2ng (nn))a)) =0 1 m (n'))))
(27)
If m/ (n())) < 1/6 + 20:
m (0) (f(n'n) 116 20 2
(28)
802
m/ 20 < <240 (nn)n)) S mr
(29)
(2 (n(n') M16 2x
241 - (nn)))
m
8
(M(r1') - -m6 20
2
- mlf
(30)
802
18

---

If m - 20 S fn(n)) < m6:
((f(n'))o)= (f'(n)) - 100 + +200)
(31)
802
nb < 2n1 - (n') S m/g + 2a
(32)
2n0 - (1())0)) = = 2210 - 8 f((((( - 1/0 - 20
-M0
2
8
-1- (M(n') - 14 + 20
1 mm(f(n')o))
(33)
8r²
If fnd)) $ md -20:
m(f"(n))) =0
(34)
2n1 ('())) 2 1/0 20
(35)
m (2ng f = =1= 11=1-m(f(n')e
(36)
Therefore, m (nf(n')lo) centrally symmetric about (101 2 Then we want to illustrate the mono- tonicity the function m(u{(o) about the variable σ, and o >
If fnn')) 2 u + 2a or (n') & mb 2a, (nf(("))()) is constant. mn 20 s fnn))) < mb.
(nf((n))oo) is monotonic increasing, because
mb M1
16 - 20 S (n()
(37)
(M(n() -m6 + 20
27
(mb (i((m)))) 22 ng + ((n'))
20
(38)
802
4
If m0 < (n') < 1b + 2o. m(f is monotonic decreasing, because
mb s (n') < 16 2o (nnn) - má
2
(f((n') 16 20 20
(f'n') -p6) (f(r)) - m/ -22
< 0
(39)
8
403
Therefore, as shown in Figure 3 P (f((m) s (nn') a) is not always decrease with a. However, on average, (f < f(n))oo) will always decrease with a. and we will prove this.
For convenience, let F(o) = P(f(m) & f(r))oo) Assume 01 < 02. then:
F(ai) - F(22) = /
[m(f(()))))) (m())))))))
x
m [m(S"nn))on) ml
mm(" ((((()))))))) P(
-m PC (
(40)
Because the function m is centrally symmetric about (MO- 2):
mff'n'))o) = - -m(2ud - f f000f(()) (n')lo)
(41)
19

---

1.0
1.0
3.0
0.8
mf (n)))
0.6
0.4
0.2
0.0
-7.5
-5.0
-2.5
0.0
2.5
5.0
7.5
("nn))
Figure Example for the monotonicity of P (f(n) s (r))))
Therefore:
0
166
mm22m - fnn))o0)) (14p---- P(F
-
(42)
F(a1)- - (((2))
Jab
80
(m((f(n')(o))) -m( (P(F((1))
(P)))))))((((( P(2p) - (()')) (n'
(43)
When f f*(n') ub- ml m(f((n'))) is monotonic decreasing with
- if it P(2))) (T()))
(44)
Because (* o()
If'(n') 1/1> 12d - fn(n') - -1f1
(45)
(s(n'') - u1)² -mf) > (2/6 - ('(n') uf) (16 mf) (F - m6) >
(46)
(47)
Assumption 4.1 gives of po. and Equation 43 only considers the situation when f* > ug.
f
Therefore Equation 47 not established and Pf (n')) 2 P(2pg -f (nn)). Therefore:
P(f((r()) - P(2 (rn))) 20
(48)
F(ai)- - (((2)) 0, σ1 <02
(49)
Therefore, F(r) is monotonic decreasing. The larger the estimation error a, the less the probability of (f()) < f()))oo)
The assumption Corollary 4.2 that the prediction enror for I" uniformly distributed quite
strong. To further illustrate the applicability of the algorithm, we also prove that Corollary 4.2 is
established if the noise follows a Gaussian distribution. Denoting Gaussian distribution as G( ), assumption regarding the distribution of the estimated values will be adjusted to:
20

---

Assumption C.1 For each node n on the optimal path, f(n) G()).0²). For nodes not on the optimal path, (n) (() o2). and (n) are independently and identically sampled from g(4, o.) Hó < so] holds because the optimal path has lower cost.
For two Gaussian distributions, have the following lemma 62 67
Lemma C.2 Assume G(u1, G( σ.) If x, independent of each other and μg > Pt, then
1 P(x > y)
1 -1)/ 03) d0.
exp
(50)
π
2
cos2
For node the optimal path, f(n 91/ 0²). For node n' off the optimal path, [(n') C( If u > (n'):
P < f(n')ld fz = T ;
1 - d0 mlf((n')oo) (51)
exp
2
20 cos²
Otherwise:
7 1/6 exp
1
1 (f 1m6)2
< S(m)lu < (r())
d0
2 20 cos
= =1 =1-m(f (m((((n))lo)
(52)
The probability that the f value of the optimal node is less than the f value of non-optimal node is
F(a) - P(F(m) < f(n')lo) = f srannen PUM"))))(((())))000000"
(53)
02 > d1:
F(oz) F(a1)=
franzn P (n()
(54)
m(f((n')o)) is symmetric about the axis (nn) = 14-
m(("(r]))==mm22 - (n())a))
(55)
Equation is equivalent to F(o2)-F(( - (P(2 -(()))-((((())) x (m(s - -m((())aai)))
(56)
According to the definition, m is monotonically increasing with respect to σ. Therefore, P(2μ) - - (nn)) (nf) tablished, and P(f(n) < [(n')o)] decreases as the prediction error a increases when the noise Gaussian distribution. The above analyses will be added to the revised paper to further elucidate the impact of prediction errors. Under both the uniform error distribution and the Gaussian error distribution, the larger the prediction error, the lower the likelihood of selecting the optimal node.
- m(f (x²))aa) -m(o'r'))) > 0. Because f*nn') ~ (ww(,o3) and mo < m/. we have
0 when f"(n)) 2 m/. Therefore, F(oz) F(a,) < 0 is es-
21

---

D Network architecture of policy and value in retrosynthesis planning
Each molecule is encoded using 2048-dimensional Morgan Fingerprint vector 45 the input for the heuristic functions. The policy network a multi-class task based on chemical reaction templates. 381302 templates are available. The policy network architecture is summarized as follows:
A fully connected layer with dimensions [2048, 512].
A batch normalization layer.
A dropout layer with dropout rate of 0.3.
Another fully connected layer with dimensions [512, 381302].
A softmax layer.
The top 50 reaction templates with the highest probabilities are retained, and corresponding chemical
reactions are generated using rdchiral package [12). an RDKit 332 wrapper for handling stereochem- istry in retrosynthetic template extraction and application.
The output of the value network is scalar estimate the synthetic cost of the input molecules. The architecture is summarized as follows:
A fully connected layer with dimensions [2048, 128).
A ReLU activation layer.
A dropout layer with dropout rate of 0.1.
A fully connected layer with dimensions [128, 1].
Normalize the output y with log(1 + e²).
Parameters of the policy and value network are the same with Retro"+ 30 No fine-tuning has been performed on the network.
E
Introduction of test molecule datasets
Besides the USPTO benchmark, six additional datasets comprising 4719 molecules are employed for robust validation. The introduction of these datasets is follows.
logP The logarithm of the partition coefficient (logP) is measure of the solubility molecule in a particular solvent. The logS of a molecule can affect the molecule's pharmacokinetics and pharmacodynamics.
logS 660 It is used to evaluate the solubility of molecules, which can affect the absorption, distribu- tion, metabolism, and excretion (ADME) of drug candidate.
Toxicity LD50 [6]]: Toxicity plays a key role determining the safety and efficacy of drugs.
Ames (25 The Ames test is commonly used in the field of drug development to evaluate the potential mutagenicity drug candidates, as well as other chemicals that may be used in drug manufacturing or as excipients.
BBBP 35): Blood-brain barrier (BBB) is a protective barrier that separates the bloodstream from the brain to prevent harmful substances from entering the brain. BBB penetration (BBBP) is considered when developing new drugs.
Clin 21: It is dataset collecting drugs approved by the FDA and drugs that have failed clinical
trials for toxicity reasons.
To clean these datasets, molecules present in either the USPTO database or the building block set are removed. Additionally, molecules that can be solved by Retro" in one step and those that can be easily solved by heuristic-based BFS planning algorithm within fixed time limit are also excluded. After processing, 4719 molecules retained.
22

---

F Search tree representation in retrosynthesis planning
The search tree employed in this paper in retrosynthesis planning problem is displayed in Figure 4 The initial state contains only the target molecule. The edges the search tree represent the chemical reactions that enable state transitions between the connected nodes, which decompose the input product into its reactants. A state is of molecules that are able synthesize the target molecule, which is decomposed from the target molecule along the traverse reaction path from the root this node. The retrosynthetic planning problem solved if all molecules within a state are available building blocks. For A singlc-step retrosynthetic prediction model is utilized as the policy model to generate potential chemical reactions yielding the input molecule. For non-terminal intermediate nodes, all molecules within the node are sorted in alphabetical order based on their SMILES representation. The first non-bute buildiig block molecule the sorted list selected as the input molecule of the single-step prediction model. The number of available reactions provided by the policy for a given node corresponds to the number of branching factors within the search tree.
Intermediate molecule
Starting building blocks
Set of reactants
Reverse reaction
100
a8)
State
{mg
Root state
Terminal solved state
(m m
[m m
Starting building blocks
Intermediate molecule
(m,, ma, ma
[m. Ma, m))
[ml Ma m1
[my myg, mys}
[1tt, m96 [1,,, myg 1y,, m3
[ma 11p. Mayl
[my 10 m[ge
[mg 12 My m0g
[m 122 Maga M2ga
(b)
Figure 4: The process involves transforming the representation of the chemical retrosynthetic route into the search tree representation used in this paper. (a) the real chemical retrosynthetic route, in which the reverse reaction decomposes the input product molecule into several reactant molecules; (b) is the corresponding search tree representation, and each node in the tree contains all molecules decomposed from the target molecule along the traverse reaction path from the root to this node.
Retro" and Retro*+ utilize the AND-OR tree as the representation for the planning process. this representation, a reaction is denoted by an AND node, with its child nodes representing the reactant molecules involved in that reaction. Similarly, a molecule is represented by an OR node, with its child nodes representing the chemical reactions capable of synthesizing that molecule. A chemical reaction can be taken all of its child reactants can be synthesized, and chemical molecule can be synthesized if there exists at least one child chemical reaction that can take place. We also applied
23

---

SeeA* to the And-OR Tree framework, and under the same settings, utilizing the uniform sampling strategy obtain candidate nodes, we observed an increase success rate from K's 91.05% to 12%1 in USPTO benchmark. The averafe siolution length is decreased from Retro*+'s 8.74 to 8.39. This finding demonstrates the effectiveness of the algorithm in the AND-OR tree structure.
G Test results on each dataset for retrosynthetic planning
Average test results the seven molecule datasets and results for the six additional testing molecule datasets are presented in Table and respectively. SeeA* achieves the maximum number of problem-solving instances and obtains the shortest solution length across all datasets.
Table 3: Test success aceuracy the seven dataset for retrosynthetic planning problem (%).
Algorithm
USPTO
logP
logS
Toxicity LD50
Ames
BBBP
ClinTox
Mean
Retro"
86.84
53.96
67.00
55.39
57.40
47.87
38.69
54.66
Retro'+
91.05
61.14
69.29
59.98
63.51
52.46
43.15
59.93
A'
88.42
58.71
68.55
59.17
62.98
51.80
42.04
58.73
WA*
84.21
58.43
68.30
59.52
62.89
52.30
44.59
58.87
MCTS
89.47
58.15
67.08
58.26
63.42
52.95
46.34
59.20
Levin'SS
96.84
61.14
70.76
60.32
64.84
54.92
43.63
61.01
PHS
87.37
55.45
65.60
57.00
59.96
50.98
39.01
56.16
e-Greedy
92.11
61.14
70.02
62.04
65.01
54.26
45.22
61.23
SeeA (Uniform)
96.84
63.37
71.00
62.73
67.32
56.39
45.70
62.97
SeeA (Cluster)
98.42
64.12
72.73
63.53
66.08
57.54
47.77
63.56
SeeA SeeA"(UUT)
98.95
63.93
72.97
63.65
65.28
56.89
47.45
63.31
Table 4: Test solution length on the seven dataset for retrosynthetic planning problem.
Algorithm
USPTO
logP
logS
ToxicityLD50
Ames
BBBP
Clin'Tox
Mean
Retro"
9.71
16.67
12.63
16.24
15.91
18.29
21.11
16.58
Retro*+
8.74
15.01
12.26
15.23
14.67
17.37
20.06
15.44
A
9.27
15.64
12.44
15.49
14.94
17.56
20.26
15.78
WA*
10.16
15.62
12.46
15.39
14.90
17.36
19.43
15.66
MCTS
8.23
16.27
13.00
15.99
15.05
17.35
19.15
15.91
LevinTSS
7.45
15.55
12.48
15.74
15.02
17.25
20.24
15.74
PHS
10.19
16.56
13.29
16.11
15.72
17.79
21.09
16.51
e-Greedy
43.78
23.21
12.76
16.70
16.32
18.43
23.82
19.88
DocA*(Uniform)
7.34
14.64
11.81
14.76
14.00
16.62
19.41
14.85
SeeA* (Cluster)
6.48
14.05
11.20
14.21
13.79
15.85
18.65
14.31
SeeA SeCA"(UUT)
6.36
14.05
11.18
14.11
13.95
16.01
18.61
14.33
H
Introduction for logic synthesis problem
Logic synthesis the process of transforming hardware design at the register transfer level (RTL) into Boolcan gate-level network, which is represented by an and-inverter-graph (AIG), i.c., netlist exclusively containing AND and NOT gates. Subsequently, a sequence of functionality- preserving transformations is applied to generate optimized AIG. Seven operations are allowed following the work of ABC [4] and other reinforcement learning algorithms balance, re- re-substitution, re-substitution of transformations limited to 10, which is the same with ABC-RL 9. Finally, post-technology mapping is performed using 7nm technology library to obtain the final netlist, which is also generated using the ABC package. Time delay and area are estimated by ABC to evaluate the solution. An example framework of solving the logic synthesis problem is presented in Figure 5
( 29), including
rewrite, rewrite -z, refactor, and refactor -z. The number

---

Input node
Output node
And gate
Original signal
Inverted signal
01
01
1
1
02
O2
2
1
03
3
O
03
A scries of transformations
13
04
Os
Post-technology mapping
05
Final AIG
Initialize AIG
ABC library
Evaluation
RTL (Verilog code)
ADP reduction
Figure 5: An example of the logic synthesis problem. The design of the hardware is represented by an and-inverter graph. After a series of transformations, more refined AIG is obtained, while maintaining the same function as original AIG. While preserving the input and output relationship, the number and connectivity of intermediate nodes optimized. Post-technology mapping and final evaluation are conducted with the ABC package.
I Introduction of the MCNC dataset
According to the partitioning in ABC-RL [9] A total of 15 circuits from the MCNC dataset [63 are utilized as training circuits, while the remaining 12 circuits from the same dataset are employed to evaluate the performance. The number of nodes in the initial AIG of each circuit ranges from hundreds to thousands. The information about the circuits summarized Ta The number of input and output nodes varies from few to several hundred, while the total number of nodes ranges from several hundred to thousands.
Table 5: Characterization of training circuits from MCNC dataset.
Circuit
# Inputs
# Outputs
# Nodes
Level
alu2
10
6
401
40
apex3
54
50
2374
21
apex5
117
88
1280
62
16
17
1814
22
c1355
41
32
504
26
c2670
233
140
717
21
c5315
178
123
1773
38
c6288
32
2337
120
frgl
28
3
126
19
i7
199
67
904
6
i8
133
81
3310
21
m3
16
434
14
max512
6
743
19
prom2
3513
22
table5
17
15
1987
26
J Value estimator for logic synthesis problem
The input of the value estimator consists the initial AIG and the sequence actions that have been taken. Nodes in the AIG And-IInveter Graph) are represented by two-dimensional vector, which
25

---

Table 6: Characterization of testing circuits from MCNC dataset.
Circuit
# Inputs
# Outputs
# Nodes
Level
alu4
10
6
735
42
apex
45
45
2655
apex2
39
3
445
29
apex4
9
19
3452
b9
41
21
105
10
c880
60
26
327
c7552
207
108
2074
29
i9
88
63
889
14
m4
8
16
760
14
pair
173
137
1500
1024
10
1021
20
proml
9
40
7803
24
records the node type and the number of inverted predecessors. The adjacency matrix is used to capture the node connectivity. Graph convolutional network (GCN) is used to extract the embedding for AIG, and the architecture is summarized as follows:
A GCN (Graph Convolutional Network) layer with a hidden size 32.
A batch normalization layer.
A LeakyReLU activation layer.
A GCN layer with hidden size of 32.
A batch normalization layer.
Mean pooling and max pooling are independently applied, and the outputs are concatenated form the final embedding, which is 64 dimension vector.
The sequence of actions and the current number of steps are combined into string, which serves as the input to the BERT model [15] to obtain a sequence embedding with 768 dimensions. AIG embedding and sequence embedding are concatenated together as the input of the value estimator, and the architecture is:
A fully connected layer with dimensions (832, 256].
A LeakyReLU activation layer.
A fully connected layer with dimensions [256, 256].
A LeakyReLU activation layer.
A fully connected layer with dimensions [256, 1].
A Tanh activation layer.
MCTS simulations are performed on the training circuits to collect samples. During the evaluation of the leaf node before backpropagation, a complete search path is obtained through a fast rollout, which is then stored as a training dataset for the value estimator. 1500 action sequences are collected for each circuit. resyn2 synthesis recipe is used the baseline during the evaluation. The area-delay product reduction for an action sequence P is defined
ADP(AIG, P)
PD = ADP(AIG, resym2)
(57)
where ADP is Area x Delay. The reward logic synthesis problem is
LADR(IIAA P)}, ift= Otherwise
R(AIG, 0,
(58)
where the index of the current step. The immediate reward is always 0 except for the last step. Therefore, the ground truth value for states in the sequence P are all equal to
26

---

max ADPR(AIG P)). Mean square enror loss is used as the learning target. Adam opti- mizer is employed update the parameter with 0.0001 learning rate. The learning process is presented in Figure
0.40
0.35
0.30
0.25
MSE
0.20
0.15
0.10
0.05
0.00
0
10000
20000
30000
40000
50000
Update
Figure 6: Training loss of the value estimator for the logic synthesis problem.
During testing, the number of the candidate nodes is fixed K 5 in uniform sampling. In the clustering sampling strategy, N₂ = clusters are employed and nodes are sampled from each cluster. The parameter 1) is set to 0.2. In the UCT-like sampling, K 5 and c 1.38.
K
An example of different search algorithms to solve logic synthesis
The search trees for A search, MCTS, and SeeA* when solving the logic synthesis problem for alu4 circuit are depicted in Figure 8 and respectively. For A search, the initial three actions are consistently "113", indicating that the search process is trapped lack of exploration. Due to the enforced exploratory nature, MCTS expands nodes across excessive branches, which can impede the efficiency of the search algorithm in generating solutions. SecA expands moderate number of branches, striking balance between the concentrated exploration of A and the excessive expansion across multiple branches in MCTS. This approach allows for exploratory behavior without being confined to single branch, while the selection of the candidate node with the minimum f-value prevents excessive expansion into irrelevant branches. As a result, SeeA* exhibits significant improvements in efficiency compared both MCTS and A".
particular branch due to
L
Value estimator for Sokoban problem
Sokoban a puzzle video game where the objective to move the crates strategically to push each crate to its corresponding storage locations. The input of the neural network is four-dimensional tensor representing the positions of the box, the target, the person, and the walls, respectively. The architecture of the value estimator is summarized as:
A convolutional layer with a kernel size of 64 3.
A batch normalization layer.
27

---

A ReLU activation layer.
A ResNet with three residual blocks.
A convolutional layer with a kernel size of x 1.
A batch normalization layer.
A ReLU activation layer.
A fully connected layer with dimensions [100, 1].
A ReLU activation layer.
The DeepCubeA paper provides 50, 000 training Sokoban problems and 1, 000 testing Sokoban problems. The A search guided by manually designed heuristic is employed to find solutions for the training problems. g is the number steps arriving at the current state. the sum distances between the boxes and their respective goals, well as the distance between the person and the nearest box. Under limited search time, 46, 252 training problems are solved. For each collected trajectory (m). ni: ... " n4. }, the learning target for state nł is the number of steps from ni to the goal state nr.
=(n)) T:
(59)
Mean square error is employed as the loss function:
I(0) E. E.E(t(nf 0) =(n)))²
(60)
Σ,
Adam optimizer with 0.0001 learning rate is used to update the parameters.
Root
d
1
2
3
4
5
d == 2
2
5
6
d=3
1
2
3
4
6
d = 4
3
4
5
Expanded nodes
d 5
2
2
3
Unexpanded nodes
27.7% 6.4%
42.7%
17.7%
1.8%
0.1%
0.1%
0.2%
Figure The search tree of A search when solving logic synthesis problem for alu4.
28

---

Root
d=2
d=3
Expanded nodes
Unexpanded nodes
0.1% 3.7% 0.1%%..%%%.%%% 18.1% 40.8% 5.8% 2.7%0.11 1.3% 0.1% 2.1%15..% 0.1%
3.2%
Figure The search tree of MCTS when solving logic synthesis problem for alu4.
Expanded nodes
Root
Unexpanded nodes
61.8%
38.2%
d=2
Same branch with A'
New branch
d d=3
different with A"
2
d=4
3
0
d d=
26.8% 3.6% 6.4%
1.4%
1.8%
0.9%
12.7%
1.4% 2.3%
0.5%
4.1%
4.3%
2.3%
0.9%
7.7%
6.8%
2.7%
Figure 9: The search tree of SeeA* search when solving logic synthesis problem for alu4.
M Test results for Sokoban problem
The search process allows maximum 10s expansions. The size of the candidate set in SecA is set to K = 100. In the clustering sampling strategy, N₂ = 2 clusters are employed and the parameter 7) is set 0.01. In the UCT-like sample, c is set 0.3. Experiment results are summarized Table 7 With the exploration behavior induced by the selective sampling, SeeA" yields shorter solutions than A" with a slight increase the number expanded nodes. By setting feasible solutions using the minimum average number of node expansions. However, the solutions by WA" tend to have longer lengths, indicating that excessive reliance on the heuristic function biases the search towards suboptimal solutions.
1.5, WA* identifies
29

---

600
400
MSE
300
200
100
10000
20000
30000
40000
Update
Figure 10: Training loss of the value estimator for the Sokoban problem.
Table 7: Test results on 1000 Sokoban cases. (Results of LevinTS, PHS, and DeepCubeA are provided by 38
39 and [1 respectively.
Algorithm
Solved
Length
Expansions
A"
100.0%
32.664
1010
WA* = 1.5)
100.0%
34.227
655
Levin'S
100.0%
39.8
6603
PHS
100.0%
39.1
2130
DeepCubeA
100.0%
32.9
1050
SeeA (Uniffom)
100.0%
32.652
1069
SeeA (Cluster)
100.0%
32.689
1130
SeeA *(UCT) 100.0%
32.505
1944
N Test results for path finding
To illustrate the effectiveness of SeeA* on problems where accurate heuristics could exist but the guiding heuristic used is unreliable, experiments on path finding are conducted, which to find the shortest path from a starting point to a destination. The cost for each step is 1. g is the number of steps taken to reach the current position, and the Euclidean distance from the current position to the target position, which is reliable enough to guide the A search in early studies. 100 robotic motion planning problems B are used to test the performance A and SeeA". Under the guidance of the same reliable h, both A and SeeA" find the optimal solutions for all testing cases, for which the average length is 400. To validate the superiority of SeeA", unreliable heuristie function is designed, which is randomly sampled from [0, x h). During the search process, nodes are evaluated by f = + h. In this situation, the average solution length of A is 691.1, much longer than SeeA *'s 531.2. Therefore, guided by an unreliable heuristie, SeeA* finds a better solution than A search, demonstrating the superiority of SeeA".
30

---

Investigations on the hyperparameters
Success rate and average solution length on the USPTO benchmark for the retrosyhthesis planning problem with different hyperparameter settings are displayed in Figure 11
12
13
1.00
16
0.95
14
0.90
0.85
Success rate
12
Avg lengi
0.80
0.75
0.70
0.65
0.60
1
5
10
30
50
80
100
200
500
1000
Candidate size K
Figure 11: Success rate and average solution length the USPTO benchmark with different candidate set sizes K in uniform sampling strategy.
1.00
16
0.95
14
0.90
0.85
Success rate
12
Avg length
0.80
0.75
10
0.70
0.65
0.60
1
2
3
4
Number of clusters N:
Figure 12: Success rate and average solution length on the USPTO benchmark with different number of clusters in clustering sampling strategy (K- 50).
31

---

1.00
0.95
14
0.90
0.85
Success rate
12
SAA leng
0.80
G+
0.75
0.70
0.65
0.60
0.005
0.01
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.5
0.8
Parameter Co
Figure 13: Success rate and average solution length on the USPTO benchmark with different in UCT-like sampling strategy (K 50).
1800
32.95
1700
32.90
1600
32.85
Avg length
1500
32.80
1400
1300
32.75
1200
32.70
1100
32.65
1000
10
20
30
50
100
150
200
250
300
350
400
450
500
600
800
1000
Candidate size K
Figure 14: Average solution length and average number of node expansions tested on the Sokoban game with different candidate sizes in uniform sampling strategy.
32

---

Ablation studies on logic synthesis are summarized below. The performance for different candidate sizes K for SeeA* with uniform sampling displayed Table The performance is robust against different K, outperforming A (K = oo) consistently.
Table 8: Test results on logic synthesis with different in uniform sampling strategy.
K
ADP reduction rate
K
ADP reduction rate
1
19.8%
20
21.2
3
22.1%
30
19.7
5
21.6%
50
19.8
10
19.8%
00
19.5
Table Test results on logic synthesis with different cs in UCT-like sampling strategy.
Cb
ADP reduction rate
Cb
ADP reduction rate
0.5
20.8% 21.8%
1.38
22.5%
1.0
1.5
22.6%
The performance for different es for UCT-like sampling is presented in Table g which is robust against different Cy. Enhanced exploration with larger leads to superior performance and longer running time.
For the sokoban game, the average solution length and the average number of node expansions for uniform sampling strategy with different candidate sizes K are presented in Figure [4] With the exploration behavior induced by the selective sampling, SeeA* yields shorter solutions than A with slight increase in the number of expanded nodes. The success rate of problem-solvin The ablation studies on the UCT-like sampling strategy are displayed in Table [T0 Under limited number of expansions, the stronger the exploration with larger Cb, the shorter the identified solution path length, and the greater the number of expansions required to find feasible solution. Sokoban permits most four legal actions at each step, which makes the number of open nodes N, grow slowly. What's more, the state space of Sokoban (10 x 10) is limited, and training reliable cost function is relatively easier compared to retrosynthetic planning. According to Theorem 4.3 larger No and less accurate cost estimator make the advantage of SeeA* more evident. Therefore, SeeA* only slightly better than A in Sokoban problem.
is 100.0%.
Table 10: Test results on Sokoban game with different e in UCT-like sampling strategy (K 100).
Cb
Solved
Length
Expansions
0.00
100.0%
32.664
1010
0.01
100.0%
32.663
1026
0.05
100.0%
32.660
1083
0.10
100.0%
32.645
1219
0.15
100.0%
32.625
1370
0.20
99.9%
32.534
1451
0.25
99.9%
32.499
1637
0.30
100.0%
32.505
1944
0.35
99.7%
32.366
1935
0.40
99.6%
32.332
2138
0.45
99.6%
32.316
2409
0.50
99.6%
32.309
2751
0.70
98.9%
32.030
3707
P Comparison between e-Greedy and SeeA* *
Both e-Greedy and SeeA* involve introducing exploration to A search. e-Greedy selects the node with the best fvauuue with probability of 1 E, and with probability of e, it randomly selects
33

---

node from the remaining nodes. SeeA* with uniform sampling strategy selects candidate set uniformly and the node with the best f value within this candidate set expanded. An example of the comparison of these two algorithms is given in Figure 15| There are five nodes {81, 82, 83, 84, 85,5,, and the values estimated by the heuristic value function are in increasing order. In A* search, node is expanded with probability of 100%. In e-Greedy (s = 0.5), there is 60% probability of expanding node $1, and each of the remaining nodes has 10% probability of being expanded. SeeA* expands 81 (the node with the smallest value) with probability of 60%. It expands $2 (the node with the second smallest f value) with a probability
30%, and 53 (the node with the third smallest value) with probability of 10%. The remaining two nodes with the largest values not eligible for expansion. Even though the selection of candidate nodes follows uniform sampling, which is quite random, only the candidate node with the smallest f value is expanded. This guarantees the quality of the expanded nodes, as nodes with significantly worse f values do not have a chance to be expanded, even if they might have been selected candidates. Assuming there are No open nodes and the size of the candidate set is K.
Open nodes
S1
S2
S3
S4
S5
Estimated heuristic value
f(,))
< f(s2)
f(33)
fS4)
f ($s))
A search
1.0
0.0
0.0
0.0
0.0
Expanded probability for g-Greedy (8 = 0.5)
0.6
0.1
0.1
0.1
0.1
Expanded probability for SeeA* with uniform sampling(K = 3)
0.6
0.3
0.1
0.0
0.0
(a)
S2, = $1 {S, S2, S43 = S1
{S1, S2, S5] = S1
P(s is expanded) 0.6
S3, S1 {S S3, S5]
{s S4, S5} = S1
{S2, S3, S4] S2 (S2, S3, 55} = S2 {S2, S4, S5} = S2
P(s is expanded) = 0.3
(S3, S4, S5] S3
P(s is expanded) 0.1
P(s is expanded) = (S55 is expanded) 0
(b)
Figure 15: (a) An example of the difference of expansion probability for each node for e-Greedy
and SeeA" (Uniform sampling strategy employed and the candidate size K 3). (b) Expanded probability calculation for SeeA". There are ten possible combinations of the candidate sets, and each combination occurs with equal probability.
34

---

The probability of expanding the node with the nth smallest f value under the uniform sampling strategy can be derived as follows:
No No
KIN. n KI. if S No K +
P(a(
(61)
O,
Otherwise
The probability of being selected for expansion decreases gradually the value increases. Com- pared to e-Greedy, SeeA" * utilizes the f' value to avoid excessive exploration in its decision process. Even though the estimated f value may be not reliable enough guarantee that the node with the smallest f value is the real optimal node to be expanded, the f value still can serve as measure of node quality within certain range. The heuristic function possesses a certain level of reliability, and it is generally inappropriate to either completely trust, like A search, or completely disregard, like e-Greedy, the evaluations provided by the heuristic function. SeeA aims achieve a balance between fully trusting and fully disregarding the evaluations of the heuristic function.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims made in the abstract and introduction accurately reflect the paper's 's contributions and scope, as illustrated in line 7 19 in the abstract and the line 47- 64 in the introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitation is pointed in the conclusion part in Line 360 367. Our algorithm is more efficient when the estimation of the heuristic function is not accurate enough. If the model exhibits precise state evaluation, the incorporation of exploration into A search becomes redundant. Investigations on more efficient sampling strategy is necessary in the future.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
36

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
The assumption and proof's are provided in the section "Efficient of SeeA*
search" and Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The algorithm is well describe in the Method section, and the pscudocode for the algorithm is provided in the Appendix A. What's more, the source code will be released after acceptance.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
37

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer:[Yee
Justification:
The source code will be published once accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips.cc/put wttpcccccppccccceee conollicggiieee gwwdggu/de/ooeo wwwedeeeeeeeebmmeeeeeeee colomisssions ssioncolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The training and test details are included in the Experiments part and Appendix G, and M.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Considering the computation resources required, the error bar is not provided in this paper, but we are trying make it available in the final version.
Guidelines:
38

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: As illustrated in the Experiments section, experiments are conducted using NVIDIA Tesla V100 GPUs and an Intel(R) Xeon(R) Gold 6238R CPU
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httph::t////// httppp/..cccppiiiitttcccuuuusuus
Answer: [Yes]
Justification: Research conducted in this paper conform with the NeurlPS code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
39

---

Justification:
The discussion on the impacts of the work is provided in the Conclusion section in Line 367 369.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: SeeA" is an efficient search algorithm, and no specific model or dataset are employed.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-uss should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
All assets used in this paper are publicly available.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
40

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thoode com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper is about new algorithm without new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
41

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "v0u3QW3V7o", "reviewer": "Reviewer_8E9W", "summary": "This work introduces a refined version of the A* search algorithm that integrates selective sampling to improve exploration & efficiency. The developed algorithm balances exploration and exploitation when heuristic guides are off the mark with the help of three sampling strategies. Also it outperforms traditional A* in both the quality of solutions and computational efficiency that is backed with practical tests.", "questions": "-\tIn Alg 1, the termination condition “until O is empty” is not clear. For some challenging problems, if a solution may not exist, will SeeA* keep expanding nodes indefinitely? Consider adding a maximum iteration limit to guarantee termination?\n-\tThe uniform sampling strategy discussed in Sec. 4.1.1 is clear and straightforward. However, the authors could discuss the potential drawbacks of this strategy, such as the possibility of selecting low-quality nodes, and how SeeA* addresses these drawbacks\n-\tThe assumption in Corollary 4.2 that the prediction error for f* is uniformly distributed is quite strong. In practice, it’s more likely non-uniform like Gaussians? More info. on the sensitivity of the theoretical results to this assumption and empirical validation of the distribution of prediction errors will be helpful\n-\tNIT: The specific f and f* values seem arbitrary in Figure 1. Are these values generalize broadly (or) are they cherry-picked? \n-\tThe authors could provide more intuition on the implications of Theorem 4.3. How does the result relate to the trade-off between exploration and exploitation in SeeA*, and how can it guide the selection of the sampling strategy or hyperparameters?\n-\tIn Sec. 5.2, the authors compare SeeA* with various baselines, including MCTS [1]. However, it is mentioned that the MCTS in [1] did not utilize any guiding heuristics. It would be informative to compare SeeA* with an MCTS variant that uses the same guiding heuristics for a fair comparison\n-\tThe hyperparameter sensitivity analysis in Sec. 5.4 provides insights on the performance of SeeA*. However, the analysis is limited to the retrosynthetic planning problem. Does this generalize to other two problem domains and beyond? \n-\tIn the Sokoban experiment (Sec. 5.3), the authors compare SeeA* with several baselines, including DeepCubeA. However, the experimental setup for DeepCubeA is not clearly stated, making it difficult to asses the fairness of the comparison.\n\nReference:\n[1] Walter Lau Neto, Yingjie Li, Pierre-Emmanuel Gaillardon, and Cunxi Yu. Flowtune: End-to-end automatic logic optimization exploration via domain-specific multi-armed bandit. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.", "limitations": "-\tThe experiment focusses solely on synthetic search problems. Initial results on real-world domain for practical applicability would be valuable\n-\tPaper provides theoretical comparison of SeeA* vs A* for uniform sampling strategy, but lacks analysis for other proposed sampling strategies.\n-\tPaper only tests on problems that don’t have inaccurate heuristics. Testing on additional domains that have unreliable heuristics would be a good addition", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Work uses multiple (3) sampling strategies to balance between exploration & exploitation for diverse scenarios\n2. Good theoretical analysis to show that the developed algorithm is efficient than traditional A* (when heuristic functions deviate from true state values)\n3. Validates the effectiveness of the algorithm through extensive experiments across multiple application\n4. Algorithm can handle large & complex search spaces (backed by experiments)", "weaknesses": "1.\tLimited theoretical analysis for some sampling strategies\n2.\tStrong assumptions in theoretical results\n3.\tExperiment represents a narrow spectrum\n4.\tScalability on resource-constrained environments/ large-scale system is not discussed\n5.\tNo sufficient details on when SeeA* fails (or) perform suboptimally", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive comments and suggestions. We will revise our paper carefully. Hope our explanation below can address your concerns.\n\nQ1: Adding a maximum iteration limit to guarantee termination.\n\nA1: Adding a limit to guarantee termination is necessary, and is adopted in our experiments. In retrosynthesis planning, search algorithms are limited to a maximum of $500$ policy calls, or $10$ minutes of running time, as mentioned in Line 271. In Sokoban, the search process is terminated if the running time exceeds $10$ minutes. We will revise Alg 1 accordingly.\n\nQ2: The potential drawbacks of uniform sampling strategy.\n\nA2: The uniform sampling strategy is easy to implement, but $P(n_1\\in\\mathcal{D})$, the probability of selecting the optimal node $n_1$ to the candidate set $\\mathcal{D}$, is relatively low, which directly impacts $P_S$, as shown in Equation 7. Therefore, additional strategies, clustering sampling and UCT-like sampling, are designed to improve $P(n_1\\in\\mathcal{D})$ by increasing the diversity of the selected nodes to avoid the excessive concentration of a few branches, thereby increasing $P(n_1\\in\\mathcal{D})$. If more information is available besides the $f$ evaluation, superior strategies can be designed, such as a specialized policy model. \n\nQ3: The assumption in Corollary 4.2 is quite strong. Prediction error is more likely non-uniform like Gaussians.\n\nA3: Thank you for your suggestion. We can prove that Corollary 4.2 also holds when noise follows a Gaussian distribution. Please refer to Global Rebuttal A1.\n\nQ4: Are f and f* values generalize broadly (or) are they cherry picked?\n\nA4: A specific example is provided in Figure 1 to illustrate that A* may be trapped in a local optimum due to insufficient exploration, which is not uncommon due to the prediction errors of guiding heuristics. Figure 7 & 9 in the appendix displayed the search tree of A* and SeeA* while solving a logic synthesis problem. A* exhibits an excessive concentration of expanded nodes in a particular non-optimal branch, which is the same as Figure 1. The superior performance of SeeA* over A* also corroborate this assertion.\n\nQ5: More intuition on the implications of Theorem 4.3.\n\nA5: Thanks for your suggestion. More detailed discussions will be added to the paper. Please refer to Global Rebuttal A2.\n\nQ6: It would be informative to compare SeeA* with an MCTS using the same guiding heuristics for a fair comparison.\n\nA6: In Table 2, the results of MCTS guided by the same heuristics as SeeA* are displayed in the PV-MCTS row, which achieves a 19.5% ADP reduction, surpassing MCTS's 18.5% but falling short of SeeA*'s 23.5%. We will further clarify the distinction between the two in the revised paper.\n\nQ7: The hyperparameter analysis is limited to the retrosynthetic planning problem. Does this generalize to other two problem domains and beyond?\n\nA7: Ablation studies on the Sokoban have been provided in the appendix. As presented in Figure 11, the performance of SeeA* is stable across a wide range of $K$. As shown in Table 8, the stronger the exploration, the shorter the identified solution path length, and the greater the number of expansions required to find a feasible solution. Due to the relatively low difficulty levels of the testing examples in the Sokoban, constructing an accurate value predictor is easier than with the other applications. Therefore, SeeA* is only slightly better than A*.\n\nAblation studies on logic synthesis are summarized below. The performance for different candidate set sizes $K$ for SeeA* with uniform sampling is displayed. The performance is robust against different $K$, outperforming A* ($K=\\infty$) consistently.\n\n|K|1|3|5|10|20|30|50|$\\infty$|\n|-|-|-|-|-|-|-|-|-|\n|ADP reduction (%)|19.8|22.1|21.6|19.8|21.2|19.7|19.8|19.5|\n\nThe performance for different $c_b$ for UCT-like sampling is as follows, which is robust against different $c_b$. enhanced exploration with a larger $c_b$ leads to superior performance and longer running time. \n\n|$c_b$|0.5|1.0|1.38|1.5|\n|-|-|-|-|-|\n|ADP reduction (%)|20.8|21.8|22.5|22.6|\n\nQ8: Paper only tests on problems that don’t have inaccurate heuristics. Testing on additional domains that have unreliable heuristics would be a good addition.\n\nA8: Thank you for your suggestion. In the paper, two applications where obtaining accurate heuristics is challenging are considered. To illustrate the effectiveness of SeeA* on problems where accurate heuristics could exist but the guiding heuristic used is unreliable, experiments on pathfinding are conducted, which is to find the shortest path from a starting point to a destination. The cost for each step is 1. $g$ is the number of steps taken to reach the current position, and $h$ is the Euclidean distance from the current position to the target position, which is reliable to guide the A* search. $100$ robotic motion planning problems [4] are used to test the performance of A* and SeeA*. Under the guidance of the same reliable $h$, both A* and SeeA* find the optimal solutions for all testing cases, for which the average length is $400$. The number of expansions of SeeA*($K=5$) with uniform sampling is $33283.21$, slightly less than the $33340.52$ of A*. To validate the superiority of SeeA*, an unreliable heuristic function $\\hat{h}$ is employed, which is randomly sampled from $[0, 2\\times h]$. During the search process, nodes are evaluated by $\\hat{f}=g+\\hat{h}$. In this situation, the average solution length of A* is $691.1$, much longer than SeeA*'s $438.4$. Moreover, A* requires $50281.28$ expansions, which is significantly more than the $32847.26$ expansions needed by SeeA*. Therefore, guided by an unreliable heuristic, SeeA* finds a better solution than A* with fewer expansions, demonstrating the superiority of SeeA*.\n\n[4] Bhardwaj, Mohak, Sanjiban Choudhury, and Sebastian Scherer. \"Learning heuristic search via imitation.\" Conference on Robot Learning. PMLR, 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K5eve2ybcb", "reviewer": "Reviewer_BBaT", "summary": "The paper introduces a method for prioritizing nodes for expansion during heuristic search that builds on A* search. However, instead of selecting the node with the lowest cost in OPEN, it samples a subset of OPEN and selects the node with the lowest cost from that subset. The sampling procedure is done using a uniform, clustering, and UCT approach. Results show that this sample based approach performs better than regular A* search. Perhaps surprising, this includes the uniform sampling method.", "questions": "Is the clustering strategy susceptible to collapsing to a single cluster? Since the initialization is purely random, it seems like this could be the case. Is there any empirical evidence to suggest this does or does not happen?\n\nHow is the heuristic function for Sokoban trained?\n\nIt seems the uniform sampling method performs better than A* search. Is there any intuition as to why? For environments with large branching factors, where deep search trees are needed, and where shortest paths are sparse, the probability of sampling a subset of OPEN that contains nodes on a shortest path would be small. Would this not hurt performance for uniform?", "limitations": "In the questions section, I describe a scenario in which random sub sampling of OPEN could hurt performance. I am not sure if this is definitely the case, but, if it is, then I would consider that a limitation.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper gives a good motivation for when sampling a subset of the OPEN list may be advantageous. In specific, this is when the heuristic function contains significant inaccuracies. The results also show the consistent superiority of this approach over A* search.", "weaknesses": "I wonder what the results would be in an environment \n\nLine 123: Step 3 also occurs if a node is associated with a state in CLOSED, but is find via a shorter path", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable feedback. We hope that our response addresses any concerns you may have.\n\nQ1:Is the clustering strategy susceptible to collapsing to a single cluster? \n\nA1: This scenario may indeed occur, and in such situations, running multiple iterations with varied initializations can be considered. Developing more efficient sampling strategies is a crucial future endeavor. In practical applications outlined in the paper, this scenario occurs infrequently in general. It occurs more often when the number of clusters is relatively low, but it may be justifiable to obtain only one cluster in some cases with fewer nodes in the search tree. For example, when the number of clusters is initialized at $5$, in the retrosynthesis task, all the generated nodes of $74$ (out of $190$) testing samples are assigned to the same one cluster after the search is terminated. The average number of node expansions to identify a feasible solution is $79.75$. When we look into the details of the $74$ samples, $53$ ones have found a feasible solution within less than $20$ expansions, and $72$ samples have found a feasible solution within less than $79.75$ expansions. What's more, increasing the number of initial cluster centers and then selecting only clusters containing nodes evenly can be a potential solution to avoid the clustering strategy collapsing to a single cluster. For the above mentioned retrosynthesis task, when the number of initial cluster centers is $20$, the number of samples with only one cluster decreases from $74$ to $41$. \n\nQ2: How is the heuristic function for Sokoban trained?\n\nA2: Training details will be added to the appendix. The DeepCubeA paper provides $50,000$ training Sokoban problems and $1,000$ testing Sokoban problems. The A* search guided by a manually designed heuristic is employed to find solutions for the training problems. $g$ is the number of steps arriving at the current state. $h$ is the sum of distances between the boxes and their destinations, along with the distance between the player and the nearest box. Under limited search time, $46,252$ training problems are solved. For each collected trajectory  $\\{n_0^i,n_1^i,\\cdots,n_t^i,\\cdots,n_{T_i}^i\\}$, the learning target for state $n_t^i$ is the number of steps from $n_t^i$ to the goal state $n_{T_i}$:\n$$z(n_t^i)=T_i-t.$$\nMean square error is employed as the loss function:\n$$L(\\theta)=\\frac{\\sum_{i}\\sum_{t}(v(n_t^i;\\theta)-z(n_t^i))^2}{\\sum_i T_i}$$\nAdam optimizer with a $0.0001$ learning rate is used to update the parameters.\n\nQ3: It seems the uniform sampling method performs better than A* search. Is there any intuition as to why? For environments with large branching factors, where deep search trees are needed, and where shortest paths are sparse, the probability of sampling a subset of OPEN that contains nodes on a shortest path would be small. Would this not hurt performance for uniform?\n\nA3: SeeA* uniformly samples candidate nodes and expands the one with the lowest $f$ value. In this setting, each nodes, except a few with the worst $f$ values, has a probability of being expanded, and the node with a smaller $f$ value still has a larger expansion likelihood, as discussed in Appendix O. SeeA* improves exploration compared to A*, but expansion remains mainly concentrated on nodes with the best $f$ values. Therefore, SeeA* achieves a balance between exploration and exploitation, making it better than A*.\n\nIf the optimal node $n_1$ is expanded by A*, $f(n_1)$ must be less than the $f$ values of all $N_o$ open nodes, while SeeA* only needs to select $n_1$ from $K$ candidate nodes if $n_1$ is included in the candidate set $\\mathcal{D}$. \n$$P_{A^*}(n_1 \\text{ is expanded})=P(n_1=\\arg\\min_{n\\in\\mathcal{O}}f(n))$$\n$$P_{SeeA^*}(n_1 \\text{ is expanded})=P(n_1=\\arg\\min_{n\\in\\mathcal{D}}f(n)|n_1\\in\\mathcal{D})P(n_1\\in\\mathcal{D})$$\nSeeA* outperforms A* if\n$$P(n_1\\in\\mathcal{D})>P(n_1=\\arg\\min_{n\\in\\mathcal{O}}f(n)) / P(n_1=\\arg\\min_{n\\in\\mathcal{D}}f(n))=p_{\\sigma}^{N_o-1}/p_{\\sigma}^{K-1}=p_{\\sigma}^{N-k}.$$\n\nAccording to Corollary 4.2, the larger the prediction error $\\sigma$, the lower the likelihood $p_{\\sigma}$ that the $f(n_1)$ is smaller than the $f$ value of a non-optimal node. $P_O=P(n_1=\\arg\\min_{n\\in\\mathcal{O}}f(n))$ is the product of $N_o-1$ probabilities, while $P_D=P(n_1=\\arg\\min_{n\\in\\mathcal{D}}f(n))$ is the product of $K-1$ probabilities. When $\\sigma$ increases, $P_O$ decreases much faster than $P_D$. The right side of the above inequality decreases. For uniform sampling, $P(n_1\\in\\mathcal{D})=K/N_o$ is irrelevant with $\\sigma$. Therefore, even with uniform sampling, SeeA* can outperform A* when $\\sigma$ are large enough.\n\nIn scenarios with large branching factors, the probability of sampling a candidate set containing optimal nodes is lower. Taking uniform sampling as an example, $P(n_1\\in\\mathcal{D})=K/N_o$ decreases as $N_o$ increases. However, the probability of A* selecting the optimal node will also decrease significantly with $N_o$ because every node has a probability of better than $n_1$. As presented in Equation 10, $H(N_o)$ approaches $1$ as $N_o$ approaches infinity, ensuring the inequality in Theorem 4.3 holds. Despite the potential decline in SeeA*'s performance with the growth of $N_o$ inevitably, it continues to outperform A*.\n\nQ4: I wonder what the results would be in an environment Line 123: Step 3 also occurs if a node is associated with a state in CLOSED, but is find via a shorter path.\n\nA4: If a node is associated with a state in CLOSED but is found via a shorter path, this node is expanded as Line 123. Experiments are conducted in retrosynthesis planning. The performance is similar to the results in the paper, and SeeA* still outperforms A* with higher success rates and shorter solution lengths.\n\n|Algorithm|Solved|Length|Expansions| \n|-|-|-|-|\n|A*|88.42%|9.28|91.27|\n|SeeA*(Uniform)|96.32%|7.44|69.21|\n|SeeA*(Cluster)|96.84%|7.04| 64.84|\n|SeeA*(UCT)|98.95%|6.36|56.87|", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HK5aNfTbpn", "reviewer": "Reviewer_KUFf", "summary": "This paper proposes a novel search strategy, SeeA*. SeeA* employs a selective sampling process to screen a dynamic candidate subset based on an additional strategy. Under certain assumptions, SeeA* theoretically has better efficiency than A* search when SeeA* uses uniform select strategy and the heuristic value function deviates substantially from the true state value function. In experiments, SeeA* outperforms state-of-the-art heuristic search algorithms in terms of problem-solving success rate and solution quality while maintaining a low level of node expansions.", "questions": "Line 116: The functions \\(\\tau\\) and \\(c\\) should be defined.\n\nFigure 1: I don't understand why this figure lists \\(n\\) with \\(10^4\\). Because \\(n_{10^4}\\) won't be explored by either algorithm. Naive A* will expand \\(n_{200}\\) at most.\n\nLine 152: I would suggest moving the algorithm part into the main paper from the appendix.\n\nLine 158: When using uniform sampling, \\(K \\to \\infty\\) means SeeA* = A*, and \\(K \\to 1\\) means SeeA* = Random Search.\n\nEquation 52: The equation contains \\(N\\) rather than \\(N_o\\), and what is lowercase \\(k\\)?\n\nLine 190: PUCT should be pUCT, and \\(Q\\) is not defined. What are the estimated \\(f\\) values? Since \\(f = g + h\\) which could be calculated directly, why do we need to estimate it?\n\nLines 201-203: I don't understand, is \\(f^*\\) sampled from Gaussian and \\(f^*\\) also sampled from Uniform?\n\nLine 215: \\(N_o\\) is not defined.\n\nEquation 8: We can get an optimal \\(K = -1/\\ln p\\). For large prediction error, \\(K \\to 1\\), random selection. For small prediction error, \\(K \\to \\infty\\), A*.\n\nTable 1: Why is uniform slower than cluster as Uniform has smaller expansions, and cluster needs additional cluster process time?\nTables 1 and 2 should indicate whether lower or higher values are better.\n\nLines 14-16: \"Theoretically establish the superior efficiency of SeeA* over A*\" should mention the theoretical analysis based on specific assumptions.\n\nAnd I'm also expecting an experiment on path search since this method is highly related to A*.", "limitations": "The strategy parameters are still hand-crafted, which may result in less dynamism when the test case distribution changes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Under certain assumptions, SeeA* theoretically has better efficiency than A* search.\n\n- Experiments on two diverse real-world applications in chemistry and circuit design, as well as one puzzle-solving game, demonstrate the efficiency of SeeA*.", "weaknesses": "- Lots of information is in the appendix rather than the main text. Some parts should be moved to the main text, such as the algorithm pseudocode and results of different parameters in section N.\n\n- Since this paper is about a traditional search algorithm and the learning part is not very clear, it may not be suitable for NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We will revise the paper accordingly and define symbols clearly. The key algorithms will be moved to the main paper. We hope that our response addresses your concerns.\n\nQ1: Why Figure 1 lists (n) with ($10^4$).\n\nA1: Setting the number of nodes to $10^4$ in the non-optimal branch is intended to demonstrate that even if the path is quite poor ($f=10^4<<f^*$), A* still spends significant efforts expanding nodes along that branch. \n\nQ2: Is ($f^*$) sampled from Gaussian and ($f^*$) also sampled from Uniform?\n\nA2: In our assumptions, the $f^*$ value is the ground truth evaluation, and $f$ aims to accurately predict $f^*$. The prediction error of $f$ with respect to $f^*$ follows a uniform distribution. The distribution of $f^*$ values for all non-optimal nodes is Gaussian. We will revise the original description to clarify the expression.\n\nQ3: Why is uniform slower than cluster as Uniform has smaller expansions, and cluster needs additional cluster process time?\n\nA3: There are primarily three parts. The first part is that competitive learning reduces the time required for clustering. One simply needs to assign each new node to the nearest center without an iterative process or re-clustering. The second part is that the time required for expanding each node varies. In retrosynthesis planning, expanding a node needs to utilize the RDKit package to reconstruct potential chemical reactions from the top $50$ chemical reaction templates selected based on the policy network. The number of chemical reactions corresponding to each reaction template varies, resulting in differences in computation time. The third part is the penalty for unresolved testing samples. If a test sample fails to identify a feasible solution, the expansion count for that sample is set to $500$, and the runtime is $600$ seconds, when calculating the mean performance listed in the table. The penalty for runtime is more severe than for expansion times. Due to the higher success rate of the Cluster sampling compared to the Uniform sampling, the discrepancy between running time and the number of expansions is possible.\n\nQ4: Experiment on path search since this method is highly related to A*.\n\nA4: Experiments on pathfinding problems are conducted using an existing heuristic function $h$ for guidance. The pathfinding problem is to find the shortest collision-free path from a starting point to a destination. The cost for each step is $1$. $g$ is the number of steps taken to reach the current position, and heuristic $h$ is the Euclidean distance from the current position to the target position, which is reliable to guide the A* search. The $100$ robotic motion planning problems [1] are used to test the performance. Under the guidance of the same reliable $h$, both A* and SeeA* find the optimal solution for all testing cases, and the average length is $400$. The number of expansions of SeeA*($K=5$) with uniform sampling is $33283.21$, slightly less than the $33340.52$ of A*. To validate the superiority of SeeA*, an unreliable heuristic function $\\hat{h}$ is employed, which is randomly sampled from $[0, 2\\times h]$. During the search process of A*, the node with the smallest $\\hat{f}=g+\\hat{h}$ is expanded. In this situation, the average solution length of A* is $691.1$, much longer than SeeA*'s $438.4$. Moreover, A* requires $50281.28$ expansions, which is significantly more than the $32847.26$ expansions needed by SeeA*. Therefore, guided by an unreliable heuristic function, SeeA* finds a better solution than A* with fewer expansions, demonstrating the superiority of SeeA*.\n\n[1] Bhardwaj, Mohak, Sanjiban Choudhury, and Sebastian Scherer. \"Learning heuristic search via imitation.\" Conference on Robot Learning 2017.\n\nQ5: This paper is about a traditional search algorithm and the learning part is not very clear.\n\nA5: We believe that our paper is suitable for NeurIPS. MCTS with help of deep learning contributed crucially the success of AlphaZero. Deep learning is also able to contribute renaissance of A*, and three possible aspects are addressed with a family of possible improvements [2]. The first and also straightforward aspect is estimating $f$ with help of deep learning, which makes current studies on A* including this paper into the era of learning aided A*. The second aspect is seeking better estimation of $f$, such as scouting before expanding the current node to collect future information to revise $f$ of the current node, which takes a crucial rule for the success of AlphaGo. The third aspect is about selecting nodes among the OPEN list that consists of open nodes of A*. It is an old tune even in the classical era of A*, but investigation is seldomly made. As shown in Appendix D, J, and L, fully connected network, convolutional network, and graph network are utilized to estimate the $h$ function.\n\nMoreover, the part of sampling strategies is related to learning distributions of open nodes. Uniform sampling approximates the distribution based on frequencies. Clustering sampling is akin to use Gaussian mixture model to learn the distribution of open nodes, where each cluster is a Gaussian. Competitive learning is adopted to assigns nodes to save computing resources. The candidate nodes are sampled from the learned distribution. \n\nWhat's more, several papers focusing on enhancements to search algorithms have been published in the past NeurIPS conferences [3,4,5,6].\n\n[2] Xu, Lei. \"Deep bidirectional intelligence: AlphaZero, deep IA-search, deep IA-infer, and TPC causal learning.\" Applied Informatics 2018.\n\n[3] Orseau, Laurent, et al. \"Single-agent policy tree search with guarantees.\" NeurIPS 2018.\n\n[4] Sokota, Samuel, et al. \"Monte carlo tree search with iteratively refining state abstractions.\" NeurIPS 2021.\n\n[5] Xiao, Chenjun, et al. \"Maximum entropy monte-carlo planning.\" NeurIPS 2019.\n\n[6] Painter, Michael, et al. \"Monte carlo tree search with boltzmann exploration.\" NeurIPS 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
A1: The assumption in Corollary 4.2 that the prediction error for $f^*$ is uniformly distributed is quite strong. To further illustrate the applicability of the algorithm, we also prove that Corollary 4.2 is established if the noise follows a Gaussian distribution. Denoting Gaussian distribution as $\mathcal{G}(\cdot,\cdot)$, Assumption 4.1 will be:

_For each node $n$ on the optimal path, $f(n)\sim\mathcal{G}(\mu_0^f,\sigma^2)$. For nodes not on the optimal path, $f(n)\sim\mathcal{G}(f^*(n),\sigma^2)$, and ${f^*(n)}$ are independently and identically sampled from $\mathcal{G}(\mu_1^f,\sigma^2_s)$. $\mu_0^f< \mu_1^f$ holds because the optimal path has a lower cost._

For two Gaussian distributions, we have the following lemma [1]:

Lemma 1: Assume $x\sim\mathcal{G}(\mu_1,\sigma_1^2)$, $y\sim\mathcal{G}(\mu_2,\sigma_2^2)$. If $x$, $y$ are independent of each other and $\mu_2>\mu_1$, then_
$$P(x>y)=\frac{1}{\pi}\int_0^{\frac{\pi}{2}}\exp\left\\{-\frac{1}{2}\frac{[(\mu_2-\mu_1)/\sqrt{\sigma_1^2+\sigma_2^2}]^2}{\cos^2\theta}\right\\}d\theta.$$
For a node $n$ on the optimal path, $f(n)\sim\mathcal{G}(\mu_0^f,\sigma^2)$. For a node $n'$ off the optimal path, $f(n')\sim\mathcal{G}(f^*(n'),\sigma^2)$. If $\mu_0^f>f^*(n')$:
$$P(f(n)<f(n')|\mu_0^f>f^*(n'))=\frac{1}{\pi}\int_0^{\frac{\pi}{2}}\exp\left\\{-\frac{1}{2}\frac{(f^*(n')-\mu_0^f)^2}{2\sigma^2\cos^2\theta}\right\\}d\theta=m(f^*(n')|\sigma)$$
Otherwise:
$$P(f(n)<f(n')|\mu_0^f<f^*(n'))=1-\frac{1}{\pi}\int_0^{\frac{\pi}{2}}\exp\left\\{-\frac{1}{2}\frac{(f^*(n')-\mu_0^f)^2}{2\sigma^2\cos^2\theta}\right\\}d\theta=1-m(f^*(n')|\sigma)$$

$$F(\sigma)=P(f(n)<f(n')|\sigma)=\int_{f^*(n')<\mu_0^f}P(f^*(n'))m(f^*(n')|\sigma)df^*(n')+\int_{f^*(n')\geq\mu_0^f}P(f^*(n'))(1-m(f^*(n')|\sigma))df^*(n')$$
If $\sigma_2>\sigma_1$:
$$F(\sigma_2)-F(\sigma_1)=\int_{f^*(n')<\mu_0^f}P(f^*(n'))(m(f^*(n')|\sigma_2)-m(f^*(n')|\sigma_1))df^*(n')+\int_{f^*(n')\geq\mu_0^f}P(f^*(n'))(m(f^*(n')|\sigma_1) - m(f^*(n')|\sigma_2))df^*(n')$$
$m(f^*(n')|\sigma)$ is symmetric about the axis $f^*(n')=\mu_0^f$, $m(f^*(n')|\sigma)=m(2\mu_0^f-f^*(n')|\sigma)$.
$$F(\sigma_2)-F(\sigma_1)=\int_{f^*(n')\geq\mu_0^f}(P(2\mu_0^f-f^*(n')) - P(f^*(n')))(m(f^*(n')|\sigma_2) - m(f^*(n')|\sigma_1))df^*(n')$$
According to the definition, $m$ is monotonically increasing with respect to $\sigma$. Therefore, $m(f^*(n')|\sigma_2) - m(f^*(n')|\sigma_1)>0$. Because $f^*(n')\sim\mathcal{N}(\mu_1^f,\sigma_2^2)$ and $\mu_0^f<\mu_1^f$, we have $P(2\mu_0^f-f^*(n'))-P(f^*(n'))<0$ when $f^*(n')\geq\mu_0^f$. Therefore, $F(\sigma_2)-F(\sigma_1)<0$ is established, and $P(f(n)<f(n')|\sigma)$ decreases as the prediction error $\sigma$ increases when the noise is Gaussian distribution. The above analyses will be added to the revised paper to further elucidate the impact of prediction errors. Under both the uniform error distribution and the Gaussian error distribution, the larger the prediction error, the lower the likelihood of selecting the optimal node.

[1] Xu, Lei, Pingfan Yan, and Tong Chang. "Algorithm cnneim-a and its mean complexity." Proc. of 2nd international conference on computers and applications. IEEE Press, Beijing. 1987.

A2: More intuition on the implications of Theorem 4.3 is provided. In Theorem 4.3, $p_{\sigma}$ is the probability that $f$ of an optimal node $n$ exceeds $f$ of a non-optimal node $n'$, 
$p_{\sigma}=P(f(n)\leq f(n')|\sigma)$. $P_S(\sigma)>P_A(\sigma)$ holds if and only if 
$$
p_{\sigma}<H(N_o,K),\quad\quad\quad H(N_o,K)=\left(\frac{K}{N_o}\right)^{\frac{1}{N_o-K}}.
$$
$p_{\sigma}$ decreases as the prediction error $\sigma$ increases. If $\sigma$ is quite small, then $p_{\sigma}$ approaches $1$, and the inequality in Theorem 4.3 is unlikely to hold. In this case, A* can identify the optimal solution efficiently without the need for candidate sampling in SeeA*. If $\sigma$ is large, estimated $f$ values are misleading, and the probability that the optimal node's $f$ value is the best among open nodes is low, possiblely even lower than random sampling. In this case, $p_{\sigma}$ is small, and the inequality holds. SeeA* is more effective than A* when $f$ is inaccurate. 

As the branching factors increase and the solution paths grow longer, the size of open set $N_o$ grows. $H(N_o,K)$ monotonically increases with respect to $N_o$. As $N_o$ approaches infinity, $H(N_o,K)$ tends to $1$, and the inequality holds. Intuitively, $n$ is expanded if its $f$ value is the smallest among open nodes. Inaccurate predictions raise the likelihood of other nodes having smaller $f$ values. As $N_o$ increases, $f(n)$ is less likely to be the smallest, leading to poorer performance of A*. SeeA* reduces the number of available nodes for selection, resulting in better performance compared to A*.

The number of candidate nodes $K$ is a key hyperparameter balancing exploration and exploitation. In SeeA*, exploitation selects the node with the best $f$ value, like A* search, while exploration uses a sampling strategy to create diverse candidate sets. If $K=1$, the selected node is determined by the sampling strategy, and SeeA* becomes random sampling. If $K\rightarrow\infty$, the candidate set is the same as the open set, and SeeA* degenerates into best-first A*. A smaller $K$ enhances exploration of SeeA*. $H(N_o,K)$ increases with $K$. If $K$ is very small, the value of $H$ will be relatively small. To ensure the inequality holds, an appropriate value of $K$ should be chosen. What's more, the probability of SeeA* expanding the optimal node as defined in Equation 8 reaches its maximum value when $K=-1/\log p_{\sigma}$, which increases with $p_{\sigma}$. For small $p_{\sigma}$, the optimal $K$ is the smallest value 1. When $p_{\sigma}$ approaches 1, the optimal $K$ will be the largest $\infty$. The choice of $K$ value is related to the prediction error $\sigma$ of the heuristic function.

Meta-review: The work builds on  two search algorithms, MCTS an A*, to introduce  a new algorithm, SeeA*, which ehnances A* with a flexible exploration-exploitation balance.  Advantages of SeeA* over A* are justified theoretically and confirmed on real-world and synthetic search domains.

The reviewers seem to agree that the paper brings a significant contribution, is written well, and provides convincing empirical evaluation supported by theoretical analysis. Some reviewers expressed concerns about strong assumptions in the theoretical analysis, but appear to have been convinced by the authors that the theoretical results hold also for more liberal assumption. One reviewer wondered whether the paper fits well within NeurIPS, and the authors justified the appropriateness of the paper for the NeurIPS audience.

The paper introduces an important but simple to grasp enhancement to a broadly used algorithm with many applications in diverse areas of machine learning and artificial intelligence. I recommend the paper for an oral presentation at the conference.
Decision: Accept (oral)