Skip to content

Pathfinder

Jump to bottom
Andrew Clements edited this page Apr 17, 2025 · 18 revisions

Pathfinder

The pathfinder program (also referred to as the search program or BFS program) is responsible for finding the shortest path between an initial configuration of modules to a final desired configuration, given a set of moves that individual modules can make. The initial and desired states can be set up in the 3D Tiler, and once a path has been found the route can be exported to a .scen file to be used in the Visualizer.

Features

  • Find the shortest path between two configurations in either 2D or 3D space
    • Can also be used to determine if such a path even exists.
  • Custom move definitions
  • Module properties
    • Properties such as color can be applied to modules, allowing for cases with more complex restrictions to be examined.
  • Support for cube and rhombic dodecahedron modules

Web vs. Desktop versions

Pathfinder is available both online through MRWT and as a desktop program. The online version is more convenient since there is no need to compile it, but since it operates within a web environment it is a bit slower and limited to only 4GiB of memory. The desktop version is also much more extensible, and can make use of advanced user-compiled properties.

For the most part, the web version should be sufficient for the tasks we had in mind when designing the system. Compiling the desktop version is a sensible option if:

  • The web version doesn't have enough memory to find a path
  • You want to use any of the following features:
    • Custom move definitions
    • Custom adjacency rules
    • Custom module properties (e.g. orientation)
    • Experimental features such as parallel pathfinding or bi-directional A*

Dependencies

When installing dependencies, it is best to use a package manager to ensure that CMake can properly find them. The recommended managers are as follows:

  • MacOS: brew
  • Linux: apt
  • Windows: vcpkg

Other managers may also work but haven't been tested.

On Windows an additional dependency is required in order for the command-line arguments to work; This dependency can be installed with $ vcpkg install getopt-win32.

Usage

Prior to running the program, JSON files will be needed to define moves that modules can make and the initial and final states. A couple move definitions are included in the repository and can be found in the Moves and Moves-Disabled directories.

Move Definitions

Movesets are defined in JSON files using the following format:

{
  "moves": [
    {
      "name": "Corner Pivot",
      "order": 2,
      "def": [[
        "xx",
        "?xx",
        "#!x"
      ]],
      "permGen": true,
      "animSeq": [
        ["pivot+y", [1, 1, 0]]
      ]
    },
    {
      "name": "Pivot",
      "order": 2,
      "def": [[
        "xx",
        "?!",
        "##"
      ]],
      "permGen": true,
      "animSeq": [
        ["pivot+y", [1, 0, 0]]
      ]
    }
  ]
}

Every moveset included in the Moves directory can be used by the search program. The Moves-Disabled directory exists as a way to conveniently disable movesets. The example shown above enables the pathfinder to use a basic pivot move and a corner pivot move. For more details on move definitions see Move Definitions.

State definitions

The initial and final states of a configuration of module are defined in terms of modules, their positions, their properties, and whether or not they are static. Examples of initial and final state definitions can be found in docs/examples, the following examples are very simple but should be sufficient to explain how the definitions work. The recommended way to set up an initial and final state is to use the 3D Tiler's export to JSON feature.

Initial State Definition:

{
  "name": "Blue Corner Move"
  "description": "Attempts to move the blue module around a corner of the black module."
  "order": 3,
  "axisSize": 5,
  "tensorPadding": 5,
  "modules": [
    {
      "position": [2, 2, 2],
      "static": true,
      "properties": {
        "colorProperty": {
          "color": "blue"
        }
      }
    },
    {
      "position": [2, 2, 3],
      "static": false,
      "properties": {
        "colorProperty": {
          "color": "black"
        }
      }
    }
  ],
  "boundaries": [
    [2, 3, 2]
  ]
}

The order and axisSize variables are used to set the size of the lattice in the search, it's important to make sure that the axis size is large enough to allow modules to move around. The modules array holds data corresponding to modules in a configuration, including their position, whether or not they are static ("static" modules may not move during the course of the search), and their properties (currently "colorProperty" is the only implemented property, but in future this could include things like orientation). The name and description variables are optional, but if defined will be used in the generation of an output scenario (.scen) file. The boundaries array holds coordinates which modules are forbidden from entering, while the tensorPadding variable determines how much padding should surround the lattice. tensorPadding should be set to the maximum distance a module can move in a single step, as this will allow bounds-checking to be skipped which improves search performance greatly. Both the boundaries and tensorPadding elements are optional, in their absence a default padding of 5 will be used.

Final State Definition:

{
  "order": 3,
  "axisSize": 5,
  "modules": [
    {
      "position": [3, 2, 2],
      "static": false,
      "properties": {
        "colorProperty": {
          "color": "black"
        }
      }
    }
  ]
}

The final state definition doesn't need to specify any static modules that were present in the initial definition since it's given that those modules will not move, although if they are specified in the final state it won't cause any issues.

Preprocessor Directives

Due to the time-complexity of shortest-path algorithms, in many places preprocessor directives are used instead of branching logic to allow the compiler to optimize as much as possible. By defining these directives when building certain features may be enabled or modified. Particularly useful directives that are likely to be used are in bold, whereas directives that are only used when debugging the program are in italic.

  • PRINT_PATH: When set to true, Pathfinder will print each step in the reconfiguration sequence to the console. This only works for 2D configurations. While this feature does work it is best to use WebVis to visualize paths. Default value: false
  • GENERATE_FINAL_STATE: When set to true, Pathfinder will generate a desired state by making random moves from the initial state, and then find the shortest path to the generated state. This may be useful for testing new move definitions, and is also perfect for determining if a configuration is rigid (rigid configurations are unable to make any moves, and as such no valid final state can be generated). Default value: false
  • LATTICE_VERBOSE: This directive controls the verbosity of the lattice. There are four levels of verbosity supported: LAT_LOG_NONE prevents the lattice from producing any output, LAT_LOG_ADJ logs adjacency information, LAT_LOG_CUT logs cut vertex / articulation point information, and LAT_LOG_ALL logs both adjacency and cut vertex information. Default value: LAT_LOG_NONE
  • LATTICE_RD_EDGECHECK: When set to true, lattice edge-checking is performed using the rhombic-dodecahedron edge checker. In order to find paths with rhombic dodecahedron modules this directive must be set to true, otherwise the single-backbone condition will immediately fail. Default value: false
  • CONFIG_PARALLEL_MOVES: When set to true, parallel moves are permitted. This increases the time complexity for generating adjacent configurations by an incredible amount, scaling exponentially with the number of non-static modules. For now, there is only one model for parallel moves currently supported: A parallel move will be permitted if and only if the modules moving in parallel have no overlapping free-space requirements. Scenario files exported in this mode will properly display the parallel moves in WebVis. Default value: false
  • CONFIG_VERBOSE: This directive controls the verbosity of the search. There are three levels of verbosity supported: CS_LOG_NONE prevents the search from producing any output, CS_LOG_FINAL_DEPTH produces output only when the search is complete, and CS_LOG_EVERY_DEPTH produces output every time the search depth changes. Default value: CS_LOG_EVERY_DEPTH
  • CONFIG_CONSISTENT_HEURISTIC_VALIDATOR: When set to true, an exception will be thrown if a heuristic exhibits non-consistent behavior during the search. If this exception is thrown when utilizing one of the built-in heuristics, please open an issue and attach the configuration files and move definitions so that the heuristic can be fixed. Default value: true
  • CONFIG_OUTPUT_JSON: When set to true, data will be gathered throughout the search and a JSON file containing the data will be produced alongside other output. This data in this file can be used to create graphs demonstrating different properties exhibited by various search methods and heuristics. Default value: false
  • MOVEMANAGER_VERBOSE: This directive controls the verbosity of the move manager. There are three levels of verbosity supported: MM_LOG_NONE prevents the move manager from producing any output, MM_LOG_MOVE_DEFS produces output relating to move definitions as they are loaded, and MM_LOG_MOVE_CHECKS produces output every time a move is checked displaying the result of the check. Default value: MM_LOG_MOVE_DEFS
  • MOVEMANAGER_BOUNDS_CHECKS: When set to true, additional checks are put in place to ensure moves don't go out-of-bounds. Since the implementation of tensor-padding with boundary space these checks were made redundant, but re-enabling them remains possible just in case. Default value: false
  • MOVEMANAGER_CHECK_BY_OFFSET: When set to true, moves are sorted and checked based on their resulting offset. This saves time when performing move checks but fails to take into consideration property updates that may happen as a result of a move. If using any moves that have associated property updates this should be set to false to ensure that moves are more closely checked. Default value: true
  • MODULEMANAGER_DATA_STORAGE: This directive controls how module data is represented. There are currently two supported representations: MM_DATA_FULL represents the modules using a complete copy of the module's coordinates and properties, and MM_DATA_INT64 represents them using a 64-bit integer. Integer representation can only be used if the module's properties can be represented flawlessly using no more than 40 bits. Additionally, integer representation limits the valid space for a module to fall within (0, 0, 0) and (255, 255, 255). Default value: MM_DATA_FULL

Compiling

To compile using CMake, first make sure that you have installed the dependencies. Once the dependencies are installed, navigate to the root directory of the project; The CMakeLists.txt file should be present here. To keep things tidy, it is recommended that you create a separate build directory.

$ mkdir ./cmake-build

Once a build directory has been created, specify the current working directory as the source directory and the newly created directory as the build directory. During this step you should also set any preprocessor directives that you need. In order to do this, simply insert -D<Directive>=<Value> after -B. If dependencies were installed using vcpkg, you will also need to set the toolchain to vcpkg by adding -DCMAKE_TOOLCHAIN_FILE="C:/vcpkg/scripts/buildsystems/vcpkg.cmake" after -B. (note: The path to vcpkg.cmake may be different on your system)

$ cmake -S . -B ./cmake-build

The executable can now be built like so:

$ cmake --build ./cmake-build --target Pathfinder

Compiling Properties

Module properties are compiled separately as shared libraries and dynamically linked at runtime. This section will describe how to build the color property. For instructions on how to build your own custom properties, see the associated wiki page.

After CMake is set up as described in the previous section, the color property can be built:

$ cmake --build ./cmake-build --target ColorPropertyLib

Running

Command Line Arguments

The pathfinder can utilize several command line arguments. Though no arguments are technically required, it is recommended to at least use -I and -F as otherwise the program itself will prompt you for paths to the state definitions, and you can't use tab to auto-complete path names at that point. The command line arguments are as follows:

  • -i Force ignore properties
  • -I <Path> Specify the file to use for the initial state definition
  • -F <Path> Specify the file to use for the final state definition
  • -e <Path> Specify the scenario file to be exported
  • -a <Path> Specify the analysis file to be exported
  • -m <Path> Specify the directory to load moves from
  • -s <Search Method> Specify the search method to be used
  • -h <Heuristic> Specify the heuristic to be used (if applicable)
Search Methods

The -s command line argument requires you to specify a search method, of which there are four available.

  • BFS or bfs for basic breadth-first search
  • BDBFS or bdbfs for bi-directional breadth-first search
  • A* or a* for A* search
  • BDA* or bda* for bi-directional A* search

In the absence of the -s argument Pathfinder will use A* by default.

Heuristics

If you are using A*, there are a variety of heuristics to choose from. To select a heuristic you will need to use the -h command line argument, with one of the following arguments:

  • "Symmetric Difference" or SymDiff, heuristic is based on the number of modules not in a desired position. Not super effective as a heuristic but very easy to prove admissibility.
  • Manhattan, heuristic is based on the Manhattan distance between the current configuration's center of mass and the desired configuration's center of mass.
  • Chebyshev, heuristic works the same way as the Manhattan heuristic except it uses Chebyshev distance instead.
  • "Nearest Chebyshev", heuristic is the sum of the Chebyshev distance of each module to the nearest desired position.
  • MRSH-1, this heuristic uses move data to create a cache which allows each module to get very good information about their best-case distance from the nearest desired position. MRSH stands for Modular Robotic System Heuristic.

Execution

To run the program, simply navigate to your build directory and run ./Pathfinder, with as many command line arguments as necessary. At this point the program is fairly hands-off, it'll perform a search of adjacent configurations until it either reaches the desired state as defined by the final state file or exhausts the search tree (meaning the desired state cannot be reached given the defined moves). If a path to the desired state was found, a scenario file will be produced to be displayed by the Visualizer.

Clone this wiki locally