An experimental comparison of planning algorithms POP and GRAPHPLAN

Planning has been an area of research in artificial intelligence for over four decades. It increases autonomy and flexibility of intelligent systems through the construction of sequences of actions to achieve their goals. In this thesis we take a look at two well known approaches to partial-order planning. The GRAPHPLAN system, which is one of the most efficient planning systems, builds a "planning graph" in a forward chaining manner. On the other hand, partial-order planners, such as POP, are goal driven. Their significant advantage over forward-chaining is that they never consider actions that are not relevant to the goal. We provide empirical evidence in favor of algorithm GRAPHPLAN, showing that it outperforms the partial-order planner, POP, on a variety of planning problems. For these two approaches we used implementations in Prolog, that can be found in Bratko's Prolog Programming for Artificial Intelligence, 4th edition. We tested them in a multi-agent planning domains. The algorithm POP needed to be fixed in order to handle correctly mutually exclusive actions. We proposed two different approaches for fixing that problem. We also considered different options for extending and performance enhancing the original algorithms: intermediate goals, bidirectional search in GRAPHPLAN, ..