TU 3: PSVN: A Hands-On Tutorial

Rob Holte

Monday June 23rd, 2014. (PM - half day)

This tutorial is a hands-on introduction to the open-source PSVN system that I have developed to study domain-independent methods for heuristic search. The PSVN language for specifying state spaces extends SAS+ in a simple but powerful way, allowing operators to be completely specified without being fully grounded. This leads to much more compact representations of many state spaces. For example, IPC problem #18 in the Scanalyzer domain has over 300,000 operators in SAS+ but requires only 65 operators in PSVN. PSVN specifications are compiled to C by the psvn2c compiler, which implements a powerful form of partial order reduction ("move pruning" (Burch and Holte, SoCS 2012)). The PSVN suite contains high-performance implementations of several search algorithms, and a substantial number of test domains (including the IPC domains translated from SAS+ to PSVN).

The tutorial is of a hands-on nature. To get the most out of it, attendees would need a laptop running Unix and with a C and C++ compiler installed, so they can download the PSVN system and work with it during the tutorial. The tutorial would begin with a brief (~45 minutes) introduction to PSVN, and then let people work individually through a sequence of tutorial lessons that will take them step by step from installing the software to writing domain-independent search algorithms that use pattern databases to define heuristics.