On the Complexity of Blocks-World Planning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Neural Logic Machines (2019, methodology): “…blocks world within the maximum m × 4 Move s. 3.4 B LOCKS W ORLD We also test NLM’s capability of decision making in the classic blocks world domain (Nilsson, 1982; Gupta & Nau, 1992) by slightly extending the model to ﬁt the formulation of Markov Decision Process (MDP) in reinforcement learning.”
Blocks World revisited (2001, methodology): “Also, the exact time complexity of nearoptimal BW planning has not been carefully analysed, [14] and [1,6] reporting respectively cubic-time and quadratic-time upper bounds in the number of blocks.”
Using temporal logics to express search control knowledge for planning (2000, methodology): “We have developed an incremental mechanism for checking whether or not a plan prefix, generated by forward chaining, could lead to a plan that satisfies an arbitrary LT formula.”
SHOP2: An HTN Planning System (2003, background): “The ability to use domain-speciﬁc problem-solving knowledge can dramatically improve a planner’s performance, and sometimes make the diﬀerence between solving a problem in exponential time and solving it in polynomial time (e.g., Gupta & Nau, 1992; Slaney & Thi´ebaux, 2001).”