English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Despite the success of practical solvers in various NP-complete domains suchas SAT and CSP as well as using deep reinforcement learning to tackletwo-player games such as Go, certain classes of PSPACE-hard planning problemshave remained out of reach. Even carefully designed domain-specialized solverscan fail quickly due to the exponential search space on hard instances. Recentworks that combine traditional search methods, such as best-first search andMonte Carlo tree search, with Deep Neural Networks' (DNN) heuristics have shownpromising progress and can solve a significant number of hard planninginstances beyond specialized solvers. To better understand why these approacheswork, we studied the interplay of the policy and value networks of DNN-basedbest-first search on Sokoban and show the surprising effectiveness of thepolicy network, further enhanced by the value network, as a guiding heuristicfor the search. To further understand the phenomena, we studied the costdistribution of the search algorithms and found that Sokoban instances can haveheavy-tailed runtime distributions, with tails both on the left and right-handsides. In particular, for the first time, we show the existence of \textit{leftheavy tails} and propose an abstract tree model that can empirically explainthe appearance of these tails. The experiments show the critical role of thepolicy network as a powerful heuristic guiding the search, which can lead toleft heavy tails with polynomial scaling by avoiding exploring exponentiallysized subtrees. Our results also demonstrate the importance of random restarts,as are widely used in traditional combinatorial solvers, for DNN-based searchmethods to avoid left and right heavy tails.

Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning