VHPOP started out as a class project for a graduate course on planning, execution, and learning at Carnegie Mellon University, taught by Reid Simmons, in the Spring of 2000. The objective of the project was to add transformational plan operators to UCPOP. It became clear to me that in order for the transformational plan operators to be effective, I needed better search control heuristics.
While at NASA Ames in the Summer of 2000, I attended an invited talk by Hector Geffner. In his talk, he mentioned some work he had done on heuristic partial order planning. I wanted to implement his heuristic, but first I decided to write a partial order planner from scratch in a typed programming language. The natural choice, being at CMU, would have been SML or Ocaml, but instead I chose C++. Based on the UCPOP code, I implemented an initial version of TPOP (Transformational Partial Order Planner) during Winter break in 2000/01 (about three weeks) while I was in Sweden.
TPOP evolved slowly during the Spring of 2001, but I never really got the transformational plan operators to work very well. Without them, the heuristic enabled me to solve more problems than before, but the planner was still not very competitive. I contacted Hector Geffner again to hear if he had had any success with his work on heuristic partial order planning. He then notified me of a paper by XuanLong Nguyen and Subbarao Kambhampati that would be published at IJCAI-01 on the revival of partial order planning. In this paper, the authors show how plan graph based heuristics can improve the performance of UCPOP. Their planner, RePOP, was shown to work quite well on some benchmark problems.
I could not reproduce their results with TPOP although I was using a similar heuristic. I suspected that the reason might be that I was still working with lifted (partially instantiated) actions while they were working with ground (fully instantiated) actions. During the Summer of 2001, I added support for ground actions in TPOP, and finally I was starting to get some promising results. During the Fall of 2001, I identified some key benefits of planning with ground actions, and this helped me to significantly improve the planner when working with lifted actions. The results of this work were published in a paper at AIPS-02.
Having improved the plan selection heuristic, I now turned to flaw selection. During another Winter break in Sweden (2001/02), I implemented a general flaw selection mechanism, and I added support for all the flaw selection strategies mentioned in a JAIR paper from 1997 by Martha Pollack, David Joslin, and Massimo Paolucci. In addition, I implemented several novel flaw selection strategies based on heuristic cost that I had been experimenting with in a less principled manner during the Fall. At this time I had completely abandoned the transformational operators, so I thought it proper to rename the planner to VHPOP (Versatile Heuristic Partial Order Planner). The first version was released in January 2002.
I then got interested in the 3rd International Planning Competition that was going to be held at AIPS-02, so I quickly added support for durative actions while I was watching the Winter Olympics on TV in Febuary 2002. Had it not been for the ridiculously bad coverage of Olympic events on U.S. network television, VHPOP might never have entered the planning competition. Entering a partial order planner into the planning competition was a gamble. I almost felt that the fate of this once dominating planning paradigm was resting on my sholders. Had VHPOP performed poorly, it might have thrust partial order planning back into darkness. Instead it earned me recognition as Best Newcomer and put partial order planners in the spotlight once again, an achievement that crowned my two-year effort with the planner.
VHPOP has never been the focus of my research, but rather just a fun project on the side. I have a few things I would like to improve or add (e.g. add support for transformational plan operators again), but it is low on my priority list. Instead I am hoping that others will find inspiration in VHPOP, and carry the torch from here.