skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Tunable Suboptimal Heuristic Search
Finding optimal solutions to state-space search problems often takes too long, even when using A* with a heuristic function. Instead, practitioners often use a tunable approach, such as weighted A*, that allows them to adjust a trade-off between search time and solution cost until the search is sufficiently fast for the intended application. In this paper, we study algorithms for this problem setting, which we call `tunable suboptimal search'. We introduce a simple baseline, called Speed*, that uses distance-to-go information to speed up search. Experimental results on standard search benchmarks suggest that 1) bounded-suboptimal searches suffer overhead due to enforcing a suboptimality bound, 2) beam searches can perform well, but fare poorly in domains with dead-ends, and 3) Speed* provides robust overall performance.  more » « less
Award ID(s):
2008594
PAR ID:
10546015
Author(s) / Creator(s):
; ;
Publisher / Repository:
AAAI Press
Date Published:
Journal Name:
Proceedings of the International Symposium on Combinatorial Search
Volume:
17
ISSN:
2832-9171
Page Range / eLocation ID:
170 to 178
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    null (Ed.)
    Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazon. CBS is a lead- ing two-level search algorithm for solving MAPF optimally. ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS by sacrificing optimality and instead guaranteeing that the costs of its solutions are within a given factor of optimal. In this paper, we study how to decrease its runtime even further using inadmissible heuristics. Motivated by Explicit Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new bounded-suboptimal variant of CBS, that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements of CBS and adapt them to EECBS. We find that EECBS with the improvements runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances. We hope that the scalability of EECBS enables additional applications for bounded-suboptimal MAPF algorithms. 
    more » « less
  2. ; (, Attention, Perception, & Psychophysics)
    Abstract People often choose suboptimal attentional control strategies during visual search. This has been at least partially attributed to the avoidance of the cognitive effort associated with the optimal strategy, but aspects of the task triggering such avoidance remain unclear. Here, we attempted to measure effort avoidance of an isolated task component to assess whether this component might drive suboptimal behavior. We adopted a modified version of the Adaptive Choice Visual Search (ACVS), a task designed to measure people’s visual search strategies. To perform optimally, participants must make a numerosity judgment—estimating and comparing two color sets—before they can advantageously search through the less numerous of the two. If participants skip the numerosity judgment step, they can still perform accurately, albeit substantially more slowly. To study whether effort associated with performing the optional numerosity judgment could be an obstacle to optimal performance, we created a variant of the demand selection task to quantify the avoidance of numerosity judgment effort. Results revealed a robust avoidance of the numerosity judgment, offering a potential explanation for why individuals choose suboptimal strategies in the ACVS task. Nevertheless, we did not find a significant relationship between individual numerosity judgment avoidance and ACVS optimality, and we discussed potential reasons for this lack of an observed relationship. Altogether, our results showed that the effort avoidance for specific subcomponents of a visual search task can be probed and linked to overall strategy choices. 
    more » « less
  3. ; ; ; ; (, The International Journal of Robotics Research)
    We present a lazy incremental search algorithm, Lifelong-GLS (L-GLS), along with its bounded suboptimal version, Bounded L-GLS (B-LGLS) that combine the search efficiency of incremental search algorithms with the evaluation efficiency of lazy search algorithms for fast replanning in problem domains where edge evaluations are more expensive than vertex expansions. The proposed algorithms generalize Lifelong Planning A* (LPA*) and its bounded suboptimal version, Truncated LPA* (TLPA*), within the Generalized Lazy Search (GLS) framework, so as to restrict expensive edge evaluations only to the current shortest subpath when the cost-to-come inconsistencies are propagated during repair. We also present dynamic versions of the L-GLS and B-LGLS algorithms, called Generalized D* (GD*) and Bounded Generalized D* (B-GD*), respectively, for efficient replanning with non-stationary queries, designed specifically for navigation of mobile robots. We prove that the proposed algorithms are complete and correct in finding a solution that is guaranteed not to exceed the optimal solution cost by a user-chosen factor. Our numerical and experimental results support the claim that the proposed integration of the incremental and lazy search frameworks can help find solutions faster compared to the regular incremental or regular lazy search algorithms when the underlying graph representation changes often. 
    more » « less
  4. ; ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    Anytime heuristic search algorithms try to find a (potentially suboptimal) solution as quickly as possible and then work to find better and better solutions until an optimal solution is obtained or time is exhausted. The most widely-known anytime search algorithms are based on best-first search. In this paper, we propose a new algorithm, rectangle search, that is instead based on beam search, a variant of breadth-first search. It repeatedly explores alternatives at all depth levels and is thus best-suited to problems featuring deep local minima. Experiments using a variety of popular search benchmarks suggest that rectangle search is competitive with fixed-width beam search and often performs better than the previous best anytime search algorithms. 
    more » « less
  5. ; ; (, 2017 IEEE GLOBECOM)
    Auction-based service provisioning and resource allocation have demonstrated strong potential in Cloud-RAN wireless network architecture and heterogeneous networks for effective resource sharing. One major technical challenge is the integration of interference constraints in auction-based solutions. In this work we transform the interference constraint requirement into a set of linear constraints on each cluster. We tackle the generally NP-hard clustering problem by developing a novel practical suboptimal solution that can meet our design requirement. Our novel algorithm utilizes the properties of chordal graphs and applies Lexicographic Breadth First Search (Lex-BFS) algorithm for cluster splitting. This polynomial time approximate algorithm searches for maximal cliques in a graph by generating strong performance in terms of subgraph density and probability of optimal clustering without suffering from the high complexity of the optimal solution. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email