Using Posthoc with Piglet

Hey FIT5222 students,

A few weeks ago, we demoed Posthoc, the pathfinding search visualiser. We’re happy to share that we’re releasing Posthoc integration for Piglet. This integration should help you analyse and understand Piglet, and pathfinding search, more effectively. Though not limited to these, Piglet integration out-of-the-box includes several visualisations such as tree, grid, graph, and nine-tile. Here’s how to use Posthoc with Piglet to enhance your pathfinding analysis.

Consider this a beta release. If you have any questions or encounter any problems, ask in our Discord or raise an issue.

Updating Piglet

Get Piglet with Posthoc visualisation support by pulling the latest version of Piglet from this repository. From your Piglet root directory, run the following:

git pull

TL;DR

Run this:

python piglet.py -p ./example/arena2.map.scen -f graph -s a-star --log trace tldr.trace.yaml -x 30 -n 1

Get this:

Example result

Open in Posthoc A* on Arena 2

Posthoc

Posthoc is a powerful tool to conduct post-hoc analysis of search algorithms. It allows you to import YAML search trace files and visualise the search process in detail. These search trace files are comprehensive descriptions that include both the process of the search and how to visualise it.

Posthoc is particularly useful when you want to visualise how your solver operates. For instance, if you are using Piglet as your solver, as long as Piglet can output YAML search traces, Posthoc can visualise it.

To recap, search traces represent your search process. A typical search trace file in YAML format looks like this:

version: 1.4.0
views:
  # Rendering instructions
  main:
    - $: rect
      alpha: 1
      fill: ${{ theme.foreground }}
      height: 1
      width: 1
      x: ${{ $.x }}
      y: ${{ $.y }}
events:
  # One or more events
  - id: DHQPrdoA
    pId: null
    type: source
    # Search progress
    f: 147.05441
    g: 0
    h: 147.05441
    # Visualisation parameters
    x: 277
    y: 186

You can render a search tree by including id and pId properties in your events. You can also specify custom views by including a views section in your search trace.

Search tree

Posthoc isn’t limited to the out-of-the-box visualisations in Piglet. Check out these Posthoc demos or the search trace documentation for more.

Generating Search Traces in Piglet

The following are new features in Piglet. Before proceeding, make sure you clone or pull the latest version of Piglet from this repository.

Piglet provides built-in support for outputting search traces. To generate these traces, you can use the --log trace argument in the command line. This argument will print the search trace directly to the console:

python piglet.py -p ./example/arena2.map.scen -f graph -s a-star --log trace -x 30 -n 1

If you’d prefer to output the trace to a file, use the --log trace filename.trace.yaml or --log trace-file argument. The trace-file argument will create a randomly named file in your current directory. If you wish, you can also use a Bash redirection operator > to direct any console output to a trace file.

python piglet.py -p ./example/arena2.map.scen -f graph -s a-star --log trace my-trace.trace.yaml -x 30 -n 1

Open in Posthoc Example on Arena 2

Since scenario files often contain hundreds of problem instances, it is helpful to use the --problem-index (-x) and --problem-number (-n) arguments to specify which specific problem to run and generate a search trace for. For example:

python piglet.py -p ./example/arena2.map.scen -f graph -s a-star --log trace -x 30 -n 1

This command will run the 30th problem instance in the specified file. Once the process is complete, you should see a file named a-star-graph-XXXXXX.trace.yaml in the current directory (or your specified filename if you used -lf). You can then drag this file into Posthoc for visualisation.

How Piglet Generates Search Traces

The logging/ and output/ sub-packages in Piglet are responsible for generating the YAML output. In search/graph_search.py and other search scripts, you’ll notice log method calls such as:

self.log("solution", current)

These calls take search nodes and eventually use the previously mentioned packages to output them as events in the YAML format.

Practical Exercises

These exercises will help you understand how to use Posthoc with Piglet in different scenarios.

Breadth-First Search (BFS) vs. Depth-First Search (DFS)

Generate search traces for breadth-first search and depth-first search using the arena2 map. Use the following commands:

python piglet.py -p ./example/arena2.map.scen -f graph -s breadth --log bfs.trace.yaml -t 0.05 -x 2 -n 1

Open in Posthoc BFS on Arena 2

python piglet.py -p ./example/arena2.map.scen -f graph -s depth --log dfs.trace.yaml -t 0.05 -x 2 -n 1

Open in Posthoc DFS on Arena 2

To limit the size of the output, a small problem instance is selected using the -x and -n arguments, and the runtime is limited to 10 milliseconds with the -t argument.

After generating the files, drag them into Posthoc.

Inspect the search in the Viewport.
Play back the search.
Use the Graph view to analyse the search.

You should observe distinct differences in the functioning of these two search techniques.

A* Search

Run the following command to generate an A* search trace and try out different visualisation features:

python piglet.py -p ./example/arena2.map.scen -f graph -s a-star --log trace-file -x 100 -n 1

Open in Posthoc A* on Arena 2

Explore the following:

Inspect the search in the Viewport.
Play back the search.

You can also experiment with different visualisations by modifying the search trace preamble. Here’s an example using the A* algorithm on an 8-tile puzzle:

python piglet.py -p ./example/example_8_puzzle.scen -f tree -s a-star --log trace-file -x 1 -n 1

Open in Posthoc 9 Tile Puzzle

Comparing A* and Weighted A* Search

See how A* search compares with A* search that uses a weighted heuristic. Run the following command, replacing WEIGHT with values such as 0, 0.5, 1.0, and 8.0:

python piglet.py -p ./example/arena2.map.scen -f graph -s a-star --heuristic-weight WEIGHT --log trace-file -x 50 -n 1

Experiment with the following:

Play back the search and observe the differences in behavior.
Use the graph’s property tracking mode to monitor the h, f, and g values.
Recall that for node n, f(n) = g(n) + h(n). Pay attention to how these values change over time and how they influence the search’s behavior.

Open in Posthoc A* 0% Heuristic Weight on Arena 2

Open in Posthoc A* 50% Heuristic Weight on Arena 2

Additional Resources

For more examples and insights on visualising search algorithms, visit the Posthoc website.

Kevin Zheng