  Knowledge-based programs (KBPs) are high-level protocols describing the
course of action an agent should perform as a function of its knowledge. The
use of KBPs for expressing action policies in AI planning has been surprisingly
overlooked. Given that to each KBP corresponds an equivalent plan and vice
versa, KBPs are typically more succinct than standard plans, but imply more
on-line computation time. Here we make this argument formal, and prove that
there exists an exponential succinctness gap between knowledge-based programs
and standard plans. Then we address the complexity of plan existence. Some
results trivially follow from results already known from the literature on
planning under incomplete knowledge, but many were unknown so far.
