[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Using Infeasibility to Improve Abstraction-Based Heuristics

  • Conference paper
Abstraction, Reformulation, and Approximation (SARA 2007)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 4612))

Abstract

The contribution of our research is to show that the accuracy of the heuristics generated by abstraction can be improved by checking for infeasibility. What do we mean by infeasible heuristics? For a state t, the heuristic value h is infeasible if it is proved that the cost of a solution for t cannot be h. Take the sliding puzzle for example, assuming that the manhattan heuristic for state t is md(t), if md(t) is even, any odd number is infeasible. To substantiate our approach, we begin with formal definitions and lemmas. Then empirical results show the effectiveness of the approach. For more details please refer to our longer work[5].

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Similar content being viewed by others

References

  1. Edelkamp, S.: Planning with pattern databases. In: Proceedings of the 6th European Conference on Planning, pp. 13–34 (2001)

    Google Scholar 

  2. Felner, A., Korf, E., Hanan, S.: Additive pattern database heuristics. Journal of Artificial Intelligence Research 22, 279–318 (2004)

    MATH  Google Scholar 

  3. Korf, E., Felner, A.: Disjoint pattern database heuristics. Artificial Intelligence 134, 9–22 (2002)

    Article  MATH  Google Scholar 

  4. Prieditis, A.E.: Machine discovery of effective admissible heuristics. Machine Learning 12, 117–141 (1993)

    Google Scholar 

  5. Yang, F., Culberson, J., Holte, R.: A general additive search abstraction. Technical Report TR07-06. Department of Computing Science, University of Alberta (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computing Science Department, University of Alberta, Edmonton, Alberta T6G 2E8, Canada

    Fan Yang, Joseph Culberson & Robert Holte

Authors
  1. Fan Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joseph Culberson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Robert Holte
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Ian Miguel Wheeler Ruml

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Yang, F., Culberson, J., Holte, R. (2007). Using Infeasibility to Improve Abstraction-Based Heuristics. In: Miguel, I., Ruml, W. (eds) Abstraction, Reformulation, and Approximation. SARA 2007. Lecture Notes in Computer Science(), vol 4612. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73580-9_41

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-73580-9_41

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-73579-3

  • Online ISBN: 978-3-540-73580-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation