Interactive storytelling (IS) is an important research topic in the broader area of interactive digital entertainment. Research in IS focuses in the search for techniques that allow the creation of systems that can generate stories that change as a consequence of a player's actions. There have been numerous articles attempting to reach this goal by employing a planning algorithm as part of the solution, but they typically do not discuss in detail why a given planning algorithm was used. Given this reality, this article makes two main contributions. First, it proposes an initial set of criteria that can be used to evaluate how well a given planning algorithm fits IS systems. Second, on the basis of these criteria, it presents an analysis using available planning systems.