skip to main content

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


This content will become publicly available on June 1, 2025

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. ; ; ; ( , Proceedings of the American Control Conference)
    Safety-guaranteed motion planning is critical for self-driving cars to generate collision-free trajectories. A layered motion planning approach with decoupled path and speed planning is widely used for this purpose. This approach is prone to be suboptimal in the presence of dynamic obstacles. Spatial-temporal approaches deal with path planning and speed planning simultaneously; however, the existing methods only support simple-shaped corridors like cuboids, which restrict the search space for optimization in complex scenarios. We propose to use trapezoidal prism-shaped corridors for optimization, which significantly enlarges the solution space compared to the existing cuboidal corridors-based method. Finally, a piecewise Bezier curve optimization is conducted in our proposed ´ corridors. This formulation theoretically guarantees the safety of the continuous-time trajectory. We validate the efficiency and effectiveness of the proposed approach in numerical and CommonRoad simulations 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email