Author name cluster

Jingwei Chen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

SoCS Conference 2022 Conference Paper

A Memory-Bounded Best-First Beam Search and Its Application to Scheduling Halide Programs

Chao Gao
Jingwei Chen
Tong Mo
Tanvir Sajed
Shangling Jui
Min Qin
Laiyuan Gong
Wei Lu 0023

Beam search is a popular algorithm for solving real-world problems --- especially where search space is an enormously large tree but real-time solutions are most preferred. We present a memory-bounded best-first beam search (MB2FBS), which can be viewed as an improved and generalized version of standard beam search in trees. The algorithm takes three parameters --- in contrast to the singular parameter beam size in standard beam search. We discuss how to recover standard beam search and how to realize other search behavior by setting these three parameters correspondingly. In particular, we show that the principal version of MB2FBS can be thought as an algorithm whose search expense is similar or upper bounded by beam search of certain beam size; however it often finds better solutions as it decides the number of nodes to be searched each depth dynamically with respect cost landscape. We apply our algorithm for tensor program auto-scheduling in Halide, an important industrial problem that uses tree search for optimizing tensor program executions. We show that the principal variants of MB2FBS deliver better empirical results than the highly optimized beam search counterpart. Most importantly, it finds superior schedules while no more computation cost is used for search, which is highly desirable for real-time program compilation and optimization.

Details

SoCS Conference 2021 Conference Paper

Avoiding Re-expansions in Suboptimal Best-First Search

Jingwei Chen
Nathan R. Sturtevant

This paper gives a summary of published conditions needed for a priority function to return bounded-optimal solutions when not performing re-expansions of previously expanded states in best-first search.

Details

AAAI Conference 2021 Conference Paper

Necessary and Sufficient Conditions for Avoiding Reopenings in Best First Suboptimal Search with General Bounding Functions

Jingwei Chen
Nathan R. Sturtevant

Recent work introduced XDP and XUP priority functions for best-first bounded-suboptimal search that do not need to perform state re-expansions as long as the search heuristic is consistent. However, that work had several limitations that are rectified here. This paper analyzes the sufficiency and necessity of the conditions used to formulate XDP and XUP. The analysis presents a simpler proof and generalizes the result in three aspects: (1) the priority function no longer has to be differentiable everywhere, (2) the quality of the solution does not have to be bounded by a constant factor, and (3) directed graphs are handled correctly. These results allow the introduction of more priority functions, such as piecewise linear functions, and more variants of bounded-suboptimal search, such as constant suboptimality. Several new priority functions are presented in this paper that, according to empirical results, can significantly outperform existing approaches including XDP.

PDF Details

ICAPS Conference 2020 Conference Paper

Predicting the Effectiveness of Bidirectional Heuristic Search

Nathan R. Sturtevant
Shahaf S. Shperberg
Ariel Felner
Jingwei Chen

The question of when bidirectional heuristic search outperforms unidirectional heuristic search has been revisited numerous times in the field of Artificial Intelligence. This paper re-addresses the question of when bidirectional search outperforms unidirectional search using an updated theoretical understanding of the problem. We show that a core set of critical states in the state space are the primary factor determining whether a bidirectional search can outperform a unidirectional search and provide simple measures to determine whether a state space and heuristic contains these critical states. We similarly discuss and show the impact that asymmetry in the underlying problem graph has on the performance of bidirectional algorithms. Experimental results show the impact of these factors on whether a problem should be solved using unidirectional or bidirectional search.

Details

IJCAI Conference 2019 Conference Paper

Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search

Jingwei Chen
Nathan R. Sturtevant

Many practical problems are too difficult to solve optimally, motivating the need to found suboptimal solutions, particularly those with bounds on the final solution quality. Algorithms like Weighted A*, A*-epsilon, Optimistic Search, EES, and DPS have been developed to find suboptimal solutions with solution quality that is within a constant bound of the optimal solution. However, with the exception of weighted A*, all of these algorithms require performing node re-expansions during search. This paper explores the properties of priority functions that can find bounded suboptimal solution without requiring node re-expansions. After general bounds are developed, two new convex priority functions are developed that can outperform weighted A*.

PDF Details

SoCS Conference 2019 Conference Paper

Revisiting Suboptimal Search

Jingwei Chen
Nathan R. Sturtevant
William J. Doyle
Wheeler Ruml

Suboptimal search algorithms can often solve much larger problems than optimal search algorithms, and thus have broad practical use. This paper returns to early algorithms like WA*, A*_e and Optimistic search. It studies the commonalities between these approaches in order to build a new bounded-suboptimal algorithm. Combined with recent research on avoiding node re-expansions in bounded-optimal search, a new solution quality bound is developed, which often provides proof of the solution bound much earlier during the search. Put together, these ideas provide a new state-of-the-art in bounded-optimal search.

Details

NeurIPS Conference 2019 Conference Paper

SCAN: A Scalable Neural Networks Framework Towards Compact and Efficient Models

Linfeng Zhang
Zhanhong Tan
Jiebo Song
Jingwei Chen
Chenglong Bao
Kaisheng Ma

Remarkable achievements have been attained by deep neural networks in various applications. However, the increasing depth and width of such models also lead to explosive growth in both storage and computation, which has restricted the deployment of deep neural networks on resource-limited edge devices. To address this problem, we propose the so-called SCAN framework for networks training and inference, which is orthogonal and complementary to existing acceleration and compression methods. The proposed SCAN firstly divides neural networks into multiple sections according to their depth and constructs shallow classifiers upon the intermediate features of different sections. Moreover, attention modules and knowledge distillation are utilized to enhance the accuracy of shallow classifiers. Based on this architecture, we further propose a threshold controlled scalable inference mechanism to approach human-like sample-specific inference. Experimental results show that SCAN can be easily equipped on various neural networks without any adjustment on hyper-parameters or neural networks architectures, yielding significant performance gain on CIFAR100 and ImageNet. Codes will be released on github soon.

PDF Details

IJCAI Conference 2017 Conference Paper

Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions

Jingwei Chen
Robert C. Holte
Sandra Zilles
Nathan R. Sturtevant

It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose f-value is smaller than the optimal solution cost when using a consistent heuristic. Such states are called “surely expanded” (s. e. ). A recent study characterized s. e. pairs of states for bidirectional search with consistent heuristics: if a pair of states is s. e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s. e. pairs, and present a new admissible front-to-end bidirectional heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.

PDF Details

AIJ Journal 2017 Journal Article

MM: A bidirectional search algorithm that is guaranteed to meet in the middle

Robert C. Holte
Ariel Felner
Guni Sharon
Nathan R. Sturtevant
Jingwei Chen

Bidirectional search algorithms interleave two separate searches, a normal search forward from the start state, and a search backward from the goal. It is well known that adding a heuristic to unidirectional search dramatically reduces the search effort. By contrast, despite decades of research, bidirectional heuristic search has not yet had a major impact. Additionally, no comprehensive theory was ever devised to understand the nature of bidirectional heuristic search. In this paper we aim to close this gap. We first present MM, a novel bidirectional heuristic search algorithm. Unlike previous bidirectional heuristic search algorithms, MM's forward and backward searches are guaranteed to “meet in the middle”, i. e. never expand a node beyond the solution midpoint. Based on this unique attribute we present a novel framework for comparing MM, A*, and their brute-force variants. We do this by dividing the entire state space into disjoint regions based on their distance from the start and goal. This allows us to perform a comparison of these algorithms on a per region basis and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.

Details DOI

ICAPS Conference 2017 Conference Paper

Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search

Jürgen Eckerle
Jingwei Chen
Nathan R. Sturtevant
Sandra Zilles
Robert C. Holte

In this paper we study bidirectional state space search with consistent heuristics, with a focus on obtaining sufficient conditions for node expansion, that is, conditions characterizing nodes that must be expanded by any admissible bidirectional search algorithm. We provide such conditions for front-to-front and front-to-end bidirectional search. The sufficient conditions are used to prove that the front-to-front bidirectional search algorithm BDS1 is optimally efficient, in terms of node expansion, among a broad class of bidirectional search algorithms, for a specific class of problem instances. Dechter and Pearl's well-known result on sufficient conditions for node expansion by unidirectional algorithms such as A* is shown to be a special case of our results.

Details

SoCS Conference 2017 Conference Paper

The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search

Eshed Shaham
Ariel Felner
Jingwei Chen
Nathan R. Sturtevant

A* is optimal among admissible unidirectional algorithms when searching with a consistent heuristic. Recently, similar optimality bounds have been established for bidirectional search, but no practical algorithm is guaranteed to always achieve this bound. In this paper we study the nature of the number of nodes that must be expanded in any front-to-end bidirectional search. We present an efficient algorithm for computing that number and show that a theoretical parameterized generalization of MM, with the correct parameter, is the optimal front-to-end bidirectional search. We then experimentally compare various algorithms and show how far they are from optimal.

Details

IJCAI Conference 2016 Conference Paper

External Memory Bidirectional Search

Nathan R. Sturtevant
Jingwei Chen

This paper studies external memory bidirectional search. That is, how bidirectional search algorithms can run using external memory such as hard drives or solid state drives. While external memory algorithms have been broadly studied in unidirectional search, they have not been studied in the context of bidirectional search. We show that the primary bottleneck in bidirectional search is the question of solution detection - knowing when the two search frontiers have met. We propose a method of delayed solution detection that makes external bidirectional search more efficient. Experimental results show the effectiveness of the approach.

PDF Details