Probably bounded suboptimal heuristic search

Roni Stern, Gal Dreiman, Richard Valenzano

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


Finding an optimal solution to a search problem is often desirable, but can be too difficult in many cases. A common approach in such cases is to try to find a solution whose suboptimality is bounded, where a parameter ϵ defines how far from optimal a solution can be while still being acceptable. A scarcely studied alternative is to try to find a solution that is probably optimal, where a parameter δ defines the confidence required in the solution's optimality. This paper explores this option and introduces the concept of a probably bounded-suboptimal search (pBS search) algorithm. Such a search algorithm accepts two parameters, ϵ and δ, and outputs a solution that with probability at least 1−δ costs at most 1+ϵ times the optimal solution. A general algorithmic framework for pBS search algorithms is proposed. Several instances of this framework are described and analyzed theoretically and experimentally on a range of search domains. Results show that pBS search algorithms are often faster than a state-of-the-art bounded-suboptimal search algorithm. This shows in practice that finding solutions that satisfy a given suboptimality bound with high probability can be done faster than finding solutions that satisfy the same suboptimality bound with certainty.

שפה מקוריתאנגלית אמריקאית
עמודים (מ-עד)39-57
מספר עמודים19
כתב עתArtificial Intelligence
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 פבר׳ 2019

ASJC Scopus subject areas

  • ???subjectarea.asjc.1200.1203???
  • ???subjectarea.asjc.3300.3310???
  • ???subjectarea.asjc.1700.1702???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Probably bounded suboptimal heuristic search'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי