Log in

Relevant bibliographies by topics / A* Heuristic Search / Journal articles

To see the other types of publications on this topic, follow the link: A* Heuristic Search.

Journal articles on the topic 'A* Heuristic Search'

Author: Grafiati

Published: 4 June 2025

Last updated: 1 August 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'A* Heuristic Search.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Wilt, Christopher, and Wheeler Ruml. "Speedy Versus Greedy Search." Proceedings of the International Symposium on Combinatorial Search 5, no. 1 (2021): 184–92. http://dx.doi.org/10.1609/socs.v5i1.18320.

Full text

Abstract:

In work on satisficing search, there has been substantial attention devoted to how to solve problems associated with local minima or plateaus in the heuristic function. One technique that has been shown to be quite promising is using an alternative heuristic function that does not estimate cost-to-go, but rather estimates distance-to-go. Empirical results generally favor using the distance-to-go heuristic over the cost-to-go heuristic, but there is currently little beyond intuition to explain the difference. We begin by empirically showing that the success of the distance-to-go heuristic appea

APA, Harvard, Vancouver, ISO, and other styles

2

Siag, Lior, Ariel Felner, and Shahaf Shperberg. "Heuristics for Bounded-Suboptimal Search." Proceedings of the International Symposium on Combinatorial Search 18 (July 19, 2025): 145–53. https://doi.org/10.1609/socs.v18i1.35986.

Full text

Abstract:

In heuristic search, it is well-established that different types of heuristics are suited for optimal heuristic search (OHS) and unbounded suboptimal search (USS). In OHS, the heuristic should minimize the error in estimating the true cost of the shortest path, whereas in USS, it is more beneficial for the heuristic to exhibit a clear gradient toward the goal, regardless of the error. However, no study has specifically investigated which heuristic is most effective for bounded suboptimal search (BSS), and the current standard is to use heuristics designed for OHS. This paper introduces a novel

APA, Harvard, Vancouver, ISO, and other styles

3

Wilt, Christopher, and Wheeler Ruml. "Effective Heuristics for Suboptimal Best-First Search." Journal of Artificial Intelligence Research 57 (October 31, 2016): 273–306. http://dx.doi.org/10.1613/jair.5036.

Full text

Abstract:

Suboptimal heuristic search algorithms such as weighted A* and greedy best-first search are widely used to solve problems for which guaranteed optimal solutions are too expensive to obtain. These algorithms crucially rely on a heuristic function to guide their search. However, most research on building heuristics addresses optimal solving. In this paper, we illustrate how established wisdom for constructing heuristics for optimal search can fail when considering suboptimal search. We consider the behavior of greedy best-first search in detail and we test several hypotheses for predicting when

APA, Harvard, Vancouver, ISO, and other styles

4

Davidov, D., and S. Markovitch. "Multiple-Goal Heuristic Search." Journal of Artificial Intelligence Research 26 (August 25, 2006): 417–51. http://dx.doi.org/10.1613/jair.1940.

Full text

Abstract:

This paper presents a new framework for anytime heuristic search where the task is to achieve as many goals as possible within the allocated resources. We show the inadequacy of traditional distance-estimation heuristics for tasks of this type and present alternative heuristics that are more appropriate for multiple-goal search. In particular, we introduce the marginal-utility heuristic, which estimates the cost and the benefit of exploring a subtree below a search node. We developed two methods for online learning of the marginal-utility heuristic. One is based on local similarity of the part

APA, Harvard, Vancouver, ISO, and other styles

5

Speck, David, Florian Geißer, and Robert Mattmüller. "When Perfect Is Not Good Enough: On the Search Behaviour of Symbolic Heuristic Search." Proceedings of the International Conference on Automated Planning and Scheduling 30 (June 1, 2020): 263–71. http://dx.doi.org/10.1609/icaps.v30i1.6670.

Full text

Abstract:

Symbolic search has proven to be a competitive approach to cost-optimal planning, as it compactly represents sets of states by symbolic data structures. While heuristics for symbolic search exist, symbolic bidirectional blind search empirically outperforms its heuristic counterpart and is therefore the dominant search strategy. This prompts the question of why heuristics do not seem to pay off in symbolic search. As a first step in answering this question, we investigate the search behaviour of symbolic heuristic search by means of BDDA⋆. Previous work identified the partitioning of state sets

APA, Harvard, Vancouver, ISO, and other styles

6

Chen, Dillon Z., and Sylvie Thiébaux. "Novelty Heuristics, Multi-Queue Search, and Portfolios for Numeric Planning." Proceedings of the International Symposium on Combinatorial Search 17 (June 1, 2024): 203–7. http://dx.doi.org/10.1609/socs.v17i1.31559.

Full text

Abstract:

Heuristic search is a powerful approach for solving planning problems and numeric planning is no exception. In this paper, we boost the performance of heuristic search for numeric planning with various powerful techniques orthogonal to improving heuristic informedness: numeric novelty heuristics, the Manhattan distance heuristic, and exploring the use of multi-queue search and portfolios for combining heuristics.

APA, Harvard, Vancouver, ISO, and other styles

7

Fišer, Daniel, Álvaro Torralba, and Jörg Hoffmann. "Operator-Potential Heuristics for Symbolic Search." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (2022): 9750–57. http://dx.doi.org/10.1609/aaai.v36i9.21210.

Full text

Abstract:

Symbolic search, using Binary Decision Diagrams (BDDs) to represent sets of states, is a competitive approach to optimal planning. Yet heuristic search in this context remains challenging. The many advances on admissible planning heuristics are not directly applicable, as they evaluate one state at a time. Indeed, progress using heuristic functions in symbolic search has been limited and even very informed heuristics have been shown to be detrimental. Here we show how this connection can be made stronger for LP-based potential heuristics. Our key observation is that, for this family of heurist

APA, Harvard, Vancouver, ISO, and other styles

8

Speck, David, André Biedenkapp, Frank Hutter, Robert Mattmüller, and Marius Lindauer. "Learning Heuristic Selection with Dynamic Algorithm Configuration." Proceedings of the International Conference on Automated Planning and Scheduling 31 (May 17, 2021): 597–605. http://dx.doi.org/10.1609/icaps.v31i1.16008.

Full text

Abstract:

A key challenge in satisficing planning is to use multiple heuristics within one heuristic search. An aggregation of multiple heuristic estimates, for example by taking the maximum, has the disadvantage that bad estimates of a single heuristic can negatively affect the whole search. Since the performance of a heuristic varies from instance to instance, approaches such as algorithm selection can be successfully applied. In addition, alternating between multiple heuristics during the search makes it possible to use all heuristics equally and improve performance. However, all these approaches ign

APA, Harvard, Vancouver, ISO, and other styles

9

Fišer, Daniel, Álvaro Torralba, and Jörg Hoffmann. "Operator-Potentials in Symbolic Search: From Forward to Bi-directional Search." Proceedings of the International Conference on Automated Planning and Scheduling 32 (June 13, 2022): 80–89. http://dx.doi.org/10.1609/icaps.v32i1.19788.

Full text

Abstract:

Symbolic search using binary decision diagrams is a state-of-the-art technique for cost-optimal planning. Heuristic search in this context has been problematic as even a very informative heuristic can be detrimental in case it induces difficult-to-represent state partitionings. It was recently shown that operator-potential heuristics can address this issue in forward search by computing a numeric potential for each operator corresponding to the change of the heuristic value induced by that operator. Forward search is, however, not the best known variant of symbolic search. Here we investigate

APA, Harvard, Vancouver, ISO, and other styles

10

Cichowicz, T., M. Drozdowski, M. Frankiewicz, G. Pawlak, F. Rytwinski, and J. Wasilewski. "Hyper-heuristics for cross-domain search." Bulletin of the Polish Academy of Sciences: Technical Sciences 60, no. 4 (2012): 801–8. http://dx.doi.org/10.2478/v10175-012-0093-7.

Full text

Abstract:

Abstract In this paper we present two hyper-heuristics developed for the Cross-Domain Heuristic Search Challenge. Hyper-heuristics solve hard combinatorial problems by guiding low level heuristics, rather than by manipulating problem solutions directly. Two hyper-heuristics are presented: Five Phase Approach and Genetic Hive. Development paths of the algorithms and testing methods are outlined. Performance of both methods is studied. Useful and interesting experience gained in construction of the hyper-heuristics are presented. Conclusions and recommendations for the future advancement of hype

APA, Harvard, Vancouver, ISO, and other styles

11

Lavasani, Sepehr, Lior Siag, Shahaf S. Shperberg, Ariel Felner, and Nathan R. Sturtevant. "Anchor Search: A Unified Framework for Suboptimal Bidirectional Search." Proceedings of the AAAI Conference on Artificial Intelligence 39, no. 25 (2025): 27045–53. https://doi.org/10.1609/aaai.v39i25.34911.

Full text

Abstract:

In recent years the understanding of optimal bidirectional heuristic search (BiHS) has progressed significantly. Yet, Bi-HS is relatively unexplored in unbounded suboptimal search. Front-to-end (F2E) and front-to-front (F2F) bidirectional search have been used in optimal algorithms, but adapting them for unbounded suboptimal search remains an open challenge. We introduce a framework for suboptimal BiHS, called anchor search, and use it to derive a parameterized family of algorithms. Because our new algorithms need F2F heuristic evaluations, we propose using pattern databases (PDBs) as differen

APA, Harvard, Vancouver, ISO, and other styles

12

Drake, John H., Matthew Hyde, Khaled Ibrahim, and Ender Ozcan. "A genetic programming hyper-heuristic for the multidimensional knapsack problem." Kybernetes 43, no. 9/10 (2014): 1500–1511. http://dx.doi.org/10.1108/k-09-2013-0201.

Full text

Abstract:

Purpose – Hyper-heuristics are a class of high-level search techniques which operate on a search space of heuristics rather than directly on a search space of solutions. The purpose of this paper is to investigate the suitability of using genetic programming as a hyper-heuristic methodology to generate constructive heuristics to solve the multidimensional 0-1 knapsack problem Design/methodology/approach – Early hyper-heuristics focused on selecting and applying a low-level heuristic at each stage of a search. Recent trends in hyper-heuristic research have led to a number of approaches being de

APA, Harvard, Vancouver, ISO, and other styles

13

Holte, Robert. "Common Misconceptions Concerning Heuristic Search." Proceedings of the International Symposium on Combinatorial Search 1, no. 1 (2010): 46–51. http://dx.doi.org/10.1609/socs.v1i1.18160.

Full text

Abstract:

This paper examines the following statements about heuristic search, which are commonly held to be true:More accurate heuristics result in fewer node expansions by A* and IDA*.A* does fewer node expansions than any other equally informed algorithm that finds optimal solutions. Any admissible heuristic can be turned into a consistent heuristic by a simple technique called pathmax.In search spaces whose operators all have the same cost A* with the heuristic function h(s)=0 for all states, s, is the same as breadth-first search.Bidirectional A* stops when the forward and backward search frontiers

APA, Harvard, Vancouver, ISO, and other styles

14

Veerapaneni, Rishi, Muhammad Suhail Saleem, and Maxim Likhachev. "Learning Local Heuristics for Search-Based Navigation Planning." Proceedings of the International Conference on Automated Planning and Scheduling 33, no. 1 (2023): 634–38. http://dx.doi.org/10.1609/icaps.v33i1.27245.

Full text

Abstract:

Graph search planning algorithms for navigation typically rely heavily on heuristics to efficiently plan paths. As a result, while such approaches require no training phase and can directly plan long horizon paths, they often require careful hand designing of informative heuristic functions. Recent works have started bypassing hand designed heuristics by using machine learning to learn heuristic functions that guide the search algorithm. While these methods can learn complex heuristic functions from raw input, they i) require significant training and ii) do not generalize well to new maps and

APA, Harvard, Vancouver, ISO, and other styles

15

Aine, Sandip, Siddharth Swaminathan, Venkatraman Narayanan, Victor Hwang, and Maxim Likhachev. "Multi-Heuristic A*." Proceedings of the International Symposium on Combinatorial Search 5, no. 1 (2021): 207–8. http://dx.doi.org/10.1609/socs.v5i1.18306.

Full text

Abstract:

We present a novel heuristic search framework, called Multi-Heuristic A* (MHA*), that simultaneously uses multiple, arbitrarily inadmissible heuristic functions and one consistent heuristic to search for complete and bounded suboptimal solutions. This simplifies the de- sign of heuristics and enables the search to effectively combine the guiding powers of different heuristic func- tions. We support these claims with experimental results on full-body manipulation for PR2 robots.

APA, Harvard, Vancouver, ISO, and other styles

16

Greco, Matias, Pablo Araneda, and Jorge A. Baier. "Focal Discrepancy Search for Learned Heuristics (Extended Abstract)." Proceedings of the International Symposium on Combinatorial Search 15, no. 1 (2022): 282–84. http://dx.doi.org/10.1609/socs.v15i1.21786.

Full text

Abstract:

Machine learning allows learning accurate but inadmissible heuristics for hard combinatorial puzzles like the 15-puzzle, the 24-puzzle, and Rubik's cube. In this paper, we investigate how to exploit these learned heuristics in the context of heuristic search with suboptimality guarantees. Specifically, we study how Focal Search (FS), a well-known bounded-suboptimal search algorithm can be modified to better exploit inadmissible learned heuristics. We propose to use Focal Discrepancy Search (FDS) in the context of learned heuristics, which uses a discrepancy function, instead of the learned heu

APA, Harvard, Vancouver, ISO, and other styles

17

Soria-Alcaraz, Jorge A., Gabriela Ochoa, Andres Espinal, Marco A. Sotelo-Figueroa, Manuel Ornelas-Rodriguez, and Horacio Rostro-Gonzalez. "A Methodology for Classifying Search Operators as Intensification or Diversification Heuristics." Complexity 2020 (February 13, 2020): 1–10. http://dx.doi.org/10.1155/2020/2871835.

Full text

Abstract:

Selection hyper-heuristics are generic search tools that dynamically choose, from a given pool, the most promising operator (low-level heuristic) to apply at each iteration of the search process. The performance of these methods depends on the quality of the heuristic pool. Two types of heuristics can be part of the pool: diversification heuristics, which help to escape from local optima, and intensification heuristics, which effectively exploit promising regions in the vicinity of good solutions. An effective search strategy needs a balance between these two strategies. However, it is not str

APA, Harvard, Vancouver, ISO, and other styles

18

Karpas, Erez, and Carmel Domshlak. "Optimal Search with Inadmissible Heuristics." Proceedings of the International Conference on Automated Planning and Scheduling 22 (May 14, 2012): 92–100. http://dx.doi.org/10.1609/icaps.v22i1.13499.

Full text

Abstract:

Considering cost-optimal heuristic search, we introduce the notion of global admissibility of a heuristic, a property weaker than standard admissibility, yet sufficient for guaranteeing solution optimality within forward search. We describe a concrete approach for creating globally admissible heuristics for domain independent planning; it is based on exploiting information gradually gathered by the search via a new form of reasoning about what we call existential optimal-plan landmarks. We evaluate our approach on some state-of-the-art heuristic search tools for cost-optimal planning, and disc

APA, Harvard, Vancouver, ISO, and other styles

19

Barley, Michael, Hans Guesgen, and Gareth Karl. "An Architecture for a Three-Tier Path-Finder." JUCS - Journal of Universal Computer Science 8, no. (8) (2002): 739–50. https://doi.org/10.3217/jucs-008-08-0739.

Full text

Abstract:

This paper describes the architecture of a route finding system that computes an optimal route between two given locations efficiently and that considers user preferences when doing so. The basis of the system is an A* algorithm that applies heuristics such as the air distance heuristic or the Manhattan heuristic to compute the shortest path between the two locations. Since A* is not tractable in general, island search is used to divide the problem into smaller problems, which can be solved more easily. In addition to that, search control rules are introduced to express user preferences about

APA, Harvard, Vancouver, ISO, and other styles

20

Chatterjee, Ishani, Maxim Likhachev, and Manuela Veloso. "Search Reduction through Conservative Abstract-Space Based Heuristic." Proceedings of the International Symposium on Combinatorial Search 8, no. 1 (2021): 161–62. http://dx.doi.org/10.1609/socs.v8i1.18420.

Full text

Abstract:

The efficiency of heuristic search depends dramatically on the quality of the heuristic function. For an optimal heuristic search, heuristics that estimate cost-to-goal better typically lead to faster searches. For a sub-optimal heuristic search such as weighted A*, the search speed depends more on the correlation between the heuristic and the true cost-to-goal. In this extended abstract, we discuss our preliminary work on computing heuristic functions that exploit this fact. In particular, we introduce a many-to-one mapping from an original search space to a conservative abstract space. Edges

APA, Harvard, Vancouver, ISO, and other styles

21

Yao, Shunyu, Fei Liu, Xi Lin, Zhichao Lu, Zhenkun Wang, and Qingfu Zhang. "Multi-Objective Evolution of Heuristic Using Large Language Model." Proceedings of the AAAI Conference on Artificial Intelligence 39, no. 25 (2025): 27144–52. https://doi.org/10.1609/aaai.v39i25.34922.

Full text

Abstract:

Heuristics are commonly used to tackle various search and optimization problems. Design heuristics usually require tedious manual crafting with domain knowledge. Recent works have incorporated Large Language Models (LLMs) into automatic heuristic search, leveraging their powerful language and coding capacity. However, existing research focuses on the optimal performance on the target problem as the sole objective, neglecting other criteria such as efficiency and scalability, which are vital in practice. To tackle this challenge, we propose to model the heuristic search as a multi-objective opt

APA, Harvard, Vancouver, ISO, and other styles

22

Wilt, Christopher, and Wheeler Ruml. "Building a Heuristic for Greedy Search." Proceedings of the International Symposium on Combinatorial Search 6, no. 1 (2021): 131–40. http://dx.doi.org/10.1609/socs.v6i1.18352.

Full text

Abstract:

Suboptimal heuristic search algorithms such as greedy best-first search allow us to find solutions when constraints of either time, memory, or both prevent the application of optimal algorithms such as A*. Guidelines for building an effective heuristic for A* are well established in the literature, but we show that if those rules are applied for greedy best-first search, performance can actually degrade. Observing what went wrong for greedy best-first search leads us to a quantitative metric appropriate for greedy heuristics, called Goal Distance Rank Correlation (GDRC). We demonstrate that GD

APA, Harvard, Vancouver, ISO, and other styles

23

Štolba, Michal, Daniel Fišer, and Antonín Komenda. "Potential Heuristics for Multi-Agent Planning." Proceedings of the International Conference on Automated Planning and Scheduling 26 (March 30, 2016): 308–16. http://dx.doi.org/10.1609/icaps.v26i1.13757.

Full text

Abstract:

Distributed heuristic search is a well established technique for multi-agent planning. It has been shown that distributed heuristics may crucially improve the search guidance, but are costly in terms of communication and computation time. One solution is to compute a heuristic additively, in the sense that each agent can compute its part of the heuristic independently and obtain a complete heuristic estimate by summing up the individual parts. In this paper, we show that the recently published potential heuristic is a good candidate for such heuristic, moreover admissible. We also demonstrate

APA, Harvard, Vancouver, ISO, and other styles

24

Sievers, Silvan, Daniel Gnad, and Álvaro Torralba. "Additive Pattern Databases for Decoupled Search." Proceedings of the International Symposium on Combinatorial Search 15, no. 1 (2022): 180–89. http://dx.doi.org/10.1609/socs.v15i1.21766.

Full text

Abstract:

Abstraction heuristics are the state of the art in optimal classical planning as heuristic search. Despite their success for explicit-state search, though, abstraction heuristics are not available for decoupled state-space search, an orthogonal reduction technique that can lead to exponential savings by decomposing planning tasks. In this paper, we show how to compute pattern database (PDB) heuristics for decoupled states. The main challenge lies in how to additively employ multiple patterns, which is crucial for strong search guidance of the heuristics. We show that in the general case, for a

APA, Harvard, Vancouver, ISO, and other styles

25

Liang, Rui Shi, and Min Huang. "Heuristics for Domain-Independent Planning: A Survey." Applied Mechanics and Materials 135-136 (October 2011): 573–77. http://dx.doi.org/10.4028/www.scientific.net/amm.135-136.573.

Full text

Abstract:

Increasing interest has been devoted to Planning as Heuristic Search over the years. Intense research has focused on deriving fast and accurate heuristics for domain-independent planning. This paper reports on an extensive survey and analysis of research work related to heuristic derivation techniques for state space search. Survey results reveal that heuristic techniques have been extensively applied in many efficient planners and result in impressive performances. We extend the survey analysis to suggest promising avenues for future research in heuristic derivation and heuristic search techn

APA, Harvard, Vancouver, ISO, and other styles

26

Greco, Matias, Jorge Toro, Carlos Hernández-Ulloa, and Jorge A. Baier. "K-Focal Search for Slow Learned Heuristics (Extended Abstract)." Proceedings of the International Symposium on Combinatorial Search 15, no. 1 (2022): 279–81. http://dx.doi.org/10.1609/socs.v15i1.21785.

Full text

Abstract:

Learned heuristics, though inadmissible, can provide very good guidance for bounded-suboptimal search. Given a single search state s and a learned heuristic h, evaluating h(s) is typically very slow relative to expansion time, since state-of-the-art learned heuristics are implemented as neural networks. However, by using a Graphics Processing Unit (GPU), it is possible to compute heuristics using batched computation. Existing approaches to batched heuristic computation are specific to satisficing search and have not studied the problem in the context of bounded-suboptimal search. In this paper

APA, Harvard, Vancouver, ISO, and other styles

27

Özcan, Ender, Mustafa Misir, Gabriela Ochoa, and Edmund K. Burke. "A Reinforcement Learning - Great-Deluge Hyper-Heuristic for Examination Timetabling." International Journal of Applied Metaheuristic Computing 1, no. 1 (2010): 39–59. http://dx.doi.org/10.4018/jamc.2010102603.

Full text

Abstract:

Hyper-heuristics can be identified as methodologies that search the space generated by a finite set of low level heuristics for solving search problems. An iterative hyper-heuristic framework can be thought of as requiring a single candidate solution and multiple perturbation low level heuristics. An initially generated complete solution goes through two successive processes (heuristic selection and move acceptance) until a set of termination criteria is satisfied. A motivating goal of hyper-heuristic research is to create automated techniques that are applicable to a wide range of problems wi

APA, Harvard, Vancouver, ISO, and other styles

28

Yiu, Ying Fung, Jing Du, and Rabi Mahapatra. "Evolutionary Heuristic A* Search: Pathfinding Algorithm with Self-Designed and Optimized Heuristic Function." International Journal of Semantic Computing 13, no. 01 (2019): 5–23. http://dx.doi.org/10.1142/s1793351x19400014.

Full text

Abstract:

The performance and efficiency of A* search algorithm heavily depends on the quality of the heuristic function. Therefore, designing an optimal heuristic function becomes the primary goal of developing a search algorithm for specific domains in artificial intelligence. However, it is difficult to design a well-constructed heuristic function without careful consideration and trial-and-error, especially for complex pathfinding problems. The complexity of a heuristic function increases and becomes unmanageable to design when an increasing number of parameters are involved. Existing approaches oft

APA, Harvard, Vancouver, ISO, and other styles

29

Seipp, Jendrik, Florian Pommerening, and Malte Helmert. "New Optimization Functions for Potential Heuristics." Proceedings of the International Conference on Automated Planning and Scheduling 25 (April 8, 2015): 193–201. http://dx.doi.org/10.1609/icaps.v25i1.13714.

Full text

Abstract:

Potential heuristics, recently introduced by Pommerening et al., characterize admissible and consistent heuristics for classical planning as a set of declarative constraints. Every feasible solution for these constraints defines an admissible heuristic, and we can obtain heuristics that optimize certain criteria such as informativeness by specifying suitable objective functions. The original paper only considered one such objective function: maximizing the heuristic value of the initial state. In this paper, we explore objectives that attempt to maximize heuristic estimates for all states (rea

APA, Harvard, Vancouver, ISO, and other styles

30

Chen, Wenlin, Yixin Chen, Kilian Weinberger, Qiang Lu, and Xiaoping Chen. "Goal-Oriented Euclidean Heuristics with Manifold Learning." Proceedings of the AAAI Conference on Artificial Intelligence 27, no. 1 (2013): 173–79. http://dx.doi.org/10.1609/aaai.v27i1.8615.

Full text

Abstract:

Recently, a Euclidean heuristic (EH) has been proposed for A* search. EH exploits manifold learning methods to construct an embedding of the state space graph, and derives an admissible heuristic distance between two states from the Euclidean distance between their respective embedded points. EH has shown good performance and memory efficiency in comparison to other existing heuristics such as differential heuristics. However, its potential has not been fully explored. In this paper, we propose a number of techniques that can significantly improve the quality of EH. We propose a goal-oriented

APA, Harvard, Vancouver, ISO, and other styles

31

Chatterjee, Ishani, Maxim Likhachev, Ashwin Khadke, and Manuela Veloso. "Speeding Up Search-Based Motion Planning via Conservative Heuristics." Proceedings of the International Conference on Automated Planning and Scheduling 29 (May 25, 2021): 674–79. http://dx.doi.org/10.1609/icaps.v29i1.3535.

Full text

Abstract:

Weighted A* search (wA*) is a popular tool for robot motionplanning. Its efficiency however depends on the quality of heuristic function used. In fact, it has been shown that the correlation between the heuristic function and the true costto-goal significantly affects the efficiency of the search, when used with a large weight on the heuristics. Motivated by this observation, we investigate the problem of computing heuristics that explicitly aim to minimize the amount of search efforts in finding a feasible plan. The key observation we exploit is that while heuristics tries to guide the search

APA, Harvard, Vancouver, ISO, and other styles

32

Höller, Daniel, Pascal Bercher, Gregor Behnke, and Susanne Biundo. "HTN Planning as Heuristic Progression Search." Journal of Artificial Intelligence Research 67 (April 21, 2020): 835–80. http://dx.doi.org/10.1613/jair.1.11282.

Full text

Abstract:

The majority of search-based HTN planning systems can be divided into those searching a space of partial plans (a plan space) and those performing progression search, i.e., that build the solution in a forward manner. So far, all HTN planners that guide the search by using heuristic functions are based on plan space search. Those systems represent the set of search nodes more effectively by maintaining a partial ordering between tasks, but they have only limited information about the current state during search. In this article, we propose the use of progression search as basis for heuristic H

APA, Harvard, Vancouver, ISO, and other styles

33

Seipp, Jendrik. "Online Saturated Cost Partitioning for Classical Planning." Proceedings of the International Conference on Automated Planning and Scheduling 31 (May 17, 2021): 317–21. http://dx.doi.org/10.1609/icaps.v31i1.15976.

Full text

Abstract:

Cost partitioning is a general method for admissibly summing up heuristic estimates for optimal state-space search. Most cost partitioning algorithms can optimize the resulting cost-partitioned heuristic for a specific state. Since computing a new cost-partitioned heuristic for each evaluated state is usually too expensive in practice, the strongest planners based on cost partitioning over abstraction heuristics precompute a set of cost-partitioned heuristics before the search and maximize over their estimates during the search. This makes state evaluations very fast, but since there is no bet

APA, Harvard, Vancouver, ISO, and other styles

34

Chen, Dillon Z., Felipe Trevizan, and Sylvie Thiébaux. "Heuristic Search for Multi-Objective Probabilistic Planning." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 10 (2023): 11945–54. http://dx.doi.org/10.1609/aaai.v37i10.26409.

Full text

Abstract:

Heuristic search is a powerful approach that has successfully been applied to a broad class of planning problems, including classical planning, multi-objective planning, and probabilistic planning modelled as a stochastic shortest path (SSP) problem. Here, we extend the reach of heuristic search to a more expressive class of problems, namely multi-objective stochastic shortest paths (MOSSPs), which require computing a coverage set of non-dominated policies. We design new heuristic search algorithms MOLAO* and MOLRTDP, which extend well-known SSP algorithms to the multi-objective case. We furth

APA, Harvard, Vancouver, ISO, and other styles

35

Larsen, Bradford, Ethan Burns, Wheeler Ruml, and Robert Holte. "Searching Without a Heuristic: Efficient Use of Abstraction." Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (2010): 114–20. http://dx.doi.org/10.1609/aaai.v24i1.7563.

Full text

Abstract:

In problem domains where an informative heuristic evaluation function is not known or not easily computed, abstraction can be used to derive admissible heuristic values. Optimal path lengths in the abstracted problem are consistent heuristic estimates for the original problem. Pattern databases are the traditional method of creating such heuristics, but they exhaustively compute costs for all abstract states and are thus usually appropriate only when all instances share the same single goal state. Hierarchical heuristic search algorithms address these shortcomings by searching for paths in the

APA, Harvard, Vancouver, ISO, and other styles

36

Kirilenko, Daniil, Anton Andreychuk, Aleksandr Panov, and Konstantin Yakovlev. "TransPath: Learning Heuristics for Grid-Based Pathfinding via Transformers." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 10 (2023): 12436–43. http://dx.doi.org/10.1609/aaai.v37i10.26465.

Full text

Abstract:

Heuristic search algorithms, e.g. A*, are the commonly used tools for pathfinding on grids, i.e. graphs of regular structure that are widely employed to represent environments in robotics, video games, etc. Instance-independent heuristics for grid graphs, e.g. Manhattan distance, do not take the obstacles into account, and thus the search led by such heuristics performs poorly in obstacle-rich environments. To this end, we suggest learning the instance-dependent heuristic proxies that are supposed to notably increase the efficiency of the search. The first heuristic proxy we suggest to learn i

APA, Harvard, Vancouver, ISO, and other styles

37

Sievers, Silvan, Martin Wehrle, Malte Helmert, and Michael Katz. "Strengthening Canonical Pattern Databases with Structural Symmetries." Proceedings of the International Symposium on Combinatorial Search 8, no. 1 (2021): 91–99. http://dx.doi.org/10.1609/socs.v8i1.18429.

Full text

Abstract:

Symmetry-based state space pruning techniques have proved to greatly improve heuristic search based classical planners. Similarly, abstraction heuristics in general and pattern databases in particular are key ingredients of such planners. However, only little work has dealt with how the abstraction heuristics behave under symmetries. In this work, we investigate the symmetry properties of the popular canonical pattern databases heuristic. Exploiting structural symmetries, we strengthen the canonical pattern databases by adding symmetric pattern databases, making the resulting heuristic invaria

APA, Harvard, Vancouver, ISO, and other styles

38

HIGGINS, A. J. "A PERCENTILE SEARCH HEURISTIC FOR GENERALIZED ASSIGNMENT PROBLEMS WITH A VERY LARGE NUMBER OF JOBS." Asia-Pacific Journal of Operational Research 22, no. 02 (2005): 171–88. http://dx.doi.org/10.1142/s0217595905000492.

Full text

Abstract:

This article presents a new heuristic for generalized assignment problems with a very large number of jobs. The heuristic applies a probabilistic acceptance of a move, based on a percentile threshold, using information from recent moves. This percentile search heuristic (PSH) is compared to tabu search, simulated annealing, and threshold accepting using a rigorous computational experimentation with randomly generated problem instances of up to 50,000 jobs and 40 agents. The PSH did find the best solution among the heuristics for 45% of the instances, particularly larger size problems, versus 3

APA, Harvard, Vancouver, ISO, and other styles

39

Abdi Oskouie, Mina, and Vadim Bulitko. "Robustness of Real-Time Heuristic Search Algorithms to Read/Write Error in Externally Stored Heuristics." Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 13, no. 1 (2021): 137–43. http://dx.doi.org/10.1609/aiide.v13i1.12943.

Full text

Abstract:

Real-time heuristic search algorithms follow the agent-centered search paradigm wherein the agent has access only to information local to the agent’s current position in the environment. This allows agents with constant-bounded computational faculties (e.g., memory) to take on search problems of progressively increasing sizes. As the agent’s memory does not scale with the size of the search problem, the heuristic must necessarily be stored externally, in the environment. Storing the heuristic in the environment brings the extra challenge of read/write errors. In video games, introducing error

APA, Harvard, Vancouver, ISO, and other styles

40

Hansen, E. A., and R. Zhou. "Anytime Heuristic Search." Journal of Artificial Intelligence Research 28 (March 9, 2007): 267–97. http://dx.doi.org/10.1613/jair.2096.

Full text

Abstract:

We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and so

APA, Harvard, Vancouver, ISO, and other styles

41

Walker, A. N. "Hybrid Heuristic Search." ICGA Journal 19, no. 1 (1996): 17–23. http://dx.doi.org/10.3233/icg-1996-19103.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Vose, Michael D. "Random heuristic search." Theoretical Computer Science 229, no. 1-2 (1999): 103–42. http://dx.doi.org/10.1016/s0304-3975(99)00120-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Al-Ayyoub, Abdel-Elah, and Fawaz A. Masoud. "Heuristic search revisited." Journal of Systems and Software 55, no. 2 (2000): 103–13. http://dx.doi.org/10.1016/s0164-1212(00)00064-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Mandow, L., and J. L. Pérez de la Cruz. "Multicriteria heuristic search." European Journal of Operational Research 150, no. 2 (2003): 253–80. http://dx.doi.org/10.1016/s0377-2217(02)00517-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Zhang, Bo, and Ling Zhang. "Statistical heuristic search." Journal of Computer Science and Technology 2, no. 1 (1987): 1–11. http://dx.doi.org/10.1007/bf02943312.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Lei, Yu, Maoguo Gong, Licheng Jiao, and Yi Zuo. "A memetic algorithm based on hyper-heuristics for examination timetabling problems." International Journal of Intelligent Computing and Cybernetics 8, no. 2 (2015): 139–51. http://dx.doi.org/10.1108/ijicc-02-2015-0005.

Full text

Abstract:

Purpose – The examination timetabling problem is an NP-hard problem. A large number of approaches for this problem are developed to find more appropriate search strategies. Hyper-heuristic is a kind of representative methods. In hyper-heuristic, the high-level search is executed to construct heuristic lists by traditional methods (such as Tabu search, variable neighborhoods and so on). The purpose of this paper is to apply the evolutionary strategy instead of traditional methods for high-level search to improve the capability of global search. Design/methodology/approach – This paper combines

APA, Harvard, Vancouver, ISO, and other styles

47

Narayanan, Venkatraman, Sandip Aine, and Maxim Likhachev. "Improved Multi-Heuristic A* for Searching with Uncalibrated Heuristics." Proceedings of the International Symposium on Combinatorial Search 6, no. 1 (2021): 78–86. http://dx.doi.org/10.1609/socs.v6i1.18350.

Full text

Abstract:

Recently, several researchers have brought forth the benefits of searching with multiple (and possibly inadmissible) heuristics, arguing how different heuristics could be independently useful in different parts of the state space. However, algorithms that use inadmissible heuristics in the traditional best-first sense, such as the recently developed Multi-Heuristic A* (MHA*), are subject to a crippling calibration problem: they prioritize nodes for expansion by additively combining the cost-to-come and the inadmissible heuristics even if those heuristics have no connection with the cost-to-go

APA, Harvard, Vancouver, ISO, and other styles

48

Drake, John H., Ender Özcan, and Edmund K. Burke. "A Case Study of Controlling Crossover in a Selection Hyper-heuristic Framework Using the Multidimensional Knapsack Problem." Evolutionary Computation 24, no. 1 (2016): 113–41. http://dx.doi.org/10.1162/evco_a_00145.

Full text

Abstract:

Hyper-heuristics are high-level methodologies for solving complex problems that operate on a search space of heuristics. In a selection hyper-heuristic framework, a heuristic is chosen from an existing set of low-level heuristics and applied to the current solution to produce a new solution at each point in the search. The use of crossover low-level heuristics is possible in an increasing number of general-purpose hyper-heuristic tools such as HyFlex and Hyperion. However, little work has been undertaken to assess how best to utilise it. Since a single-point search hyper-heuristic operates on

APA, Harvard, Vancouver, ISO, and other styles

49

Özçağdavul, Mazlum. "A COMPREHENSIVE ANALYSIS OF MULTI-STRATEGY MEMETIC ALGORITHMS INCORPORATING LOW-LEVEL HEURISTICS AND ACCEPTANCE MECHANISMS." AYBU Business Journal 4, no. 1 (2024): 1–23. http://dx.doi.org/10.61725/abj.1499654.

Full text

Abstract:

Hyper-heuristics are designed to be reusable, domain-independent methods for addressing complex computational issues. While there are specialized approaches that work well for particular problems, they often require parameter tuning and cannot be transferred to other problems. Memetic Algorithms combine genetic algorithms and local search techniques. The evolutionary interaction of memes allows for the creation of intelligent complexes capable of solving computational problems. Hyper-heuristics are a high-level search technique that operates on a set of low-level heuristics that directly addre

APA, Harvard, Vancouver, ISO, and other styles

50

Rayner, D. Chris, Michael Bowling, and Nathan Sturtevant. "Euclidean Heuristic Optimization." Proceedings of the AAAI Conference on Artificial Intelligence 25, no. 1 (2011): 81–86. http://dx.doi.org/10.1609/aaai.v25i1.7815.

Full text

Abstract:

We pose the problem of constructing good search heuristics as an optimization problem: minimizing the loss between the true distances and the heuristic estimates subject to admissibility and consistency constraints. For a well-motivated choice of loss function, we show performing this optimization is tractable. In fact, it corresponds to a recently proposed method for dimensionality reduction. We prove this optimization is guaranteed to produce admissible and consistent heuristics, generalizes and gives insight into differential heuristics, and show experimentally that it produces strong heuri

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!