Using discopygal package

In this page it will be explained what the discopygal package contains and how to use it when writing scripts.

The main abilities of the package are:

Create scenes and visualize them
Create motion planning algorithms
Environment to check and visualize the motion planning algorithms on actual scenes

1. How to use the package?

Once installed (in virtual environment or directly on regular environment) the package can be imported from anywhere as a regular package:

import discopygal

or with the “from” syntax for specific modules:

from discopygal... import ...

If the package was installed in virtual env don’t forget to activate it first:

pipenv shell

To deactivate:

exit

If working with an IDE it is also possible to run your scripts from there like any other script. Again, if using virtual env configure first the python interpreter in your IDE to be the right one from the virtual env. If using pipenv, the python interpreter of the virtual env will be found at:

/home/<User name>/.virtualenvs/<virtual env name>/bin/python

C:\Users\<User name>\.virtualenvs\<virtual env name>\Scripts\python.exe

2. Components

As can be seen in these docs, the package consists of the following components:

bindings - Imports from CGALPY that discopygal uses: CGALPY Bindings
experiments - Utilities for conducting experiments: Experiments Utilities
gui - GUI utilities for visualizations: GUI Documentation
geometry_utils - Basic computational geometric functions: Geometry Utilities
solvers_infra - Infrastructure and utilities required for creating a solver for motion planning (like base classes): Solvers Infrastructure
solvers - Actual motion planning solving algorithms: Solvers

3. Creating a solver

One of the main options discopygal offers is an opportunity to write your own motion planning algorithm which is referred as “Solver”.
Discopygal has a basic solver class discopygal.solvers_infra.Solver.Solver which every solver must inherit from.
Therefore, a solver is simply a class that inherits from Solver and implements a motion planning algorithm.
In every solver class it is required to implement the following functions:

discopygal.solvers_infra.Solver.Solver.load_scene() - The function that gets a scene object and does necessary preprocessing if needed. Call the base function to save the scene in scene
discopygal.solvers_infra.Solver.Solver._solve() - The function that solves the loaded scene, plans the motion and returns the robots’ paths
discopygal.solvers_infra.Solver.Solver.get_arguments() - Return a dict of all needed arguments (parameters) by the solver in the following form
{ argument_name: (description, default value, type), ... }
- argument_name: The name of the solver’s attribute
  
  Important
  
  Note that the corresponding parameter in the __init__() function of the solver must also have also this name
- description: The label that will be seen in the gui
- default value: The default value that will be set for this argument
- type: The type of the argument
discopygal.solvers_infra.Solver.Solver.get_graph() (Optional) - Return all the constructed graph (can be viewed in solver_viewer)
discopygal.solvers_infra.Solver.Solver.get_arrangement() (Optional) - Return an arrangement (can be viewed in solver_viewer)

After creating your solver class, you can initialize solver objects from it and use them directly to solve scenes or load them to Solver viewer and use them there.

Check the Solver class documentation for a list of all the functions it contains.

3.1. Examples

Here are some basic examples to understand how to build a solver class and use it.

Read all of them since they all together show the various options and ways to use the module.

3.1.1. Empty Solver

An empty solver that doesn’t do anything, it doesn’t return any paths and therefore of course doesn’t really solve the scene. It shows the minium functions that need to be implemented to create a valid solver

from discopygal.solvers_infra.Solver import Solver


class EmptySolver(Solver):
    def _solve(self):
        self.log("Solving...")
        return None

    # Not really need this
    def load_scene(self, scene):
        super().load_scene(scene)

    @classmethod
    def get_arguments(cls):
        return {}

3.1.2. Basic Solver

A basic solver the implements _solve() function in a naive way.

BasicSolver Class code

BasicSolver.py

from discopygal.solvers_infra.Solver import Solver
from discopygal.solvers_infra import PathCollection, RobotRod, Path, PathPoint


class BasicSolver(Solver):
    """
    A basic solver example which it's solution paths are just a straight line from start point to end point
    (which is usually not valid).

    It has no arguments and doesn't use a bounding box.
    Doesn't do any special pre-processing when loading a scene (only the default :func:`load_scene` is invoked)
    """
    def __init__(self):
        # Don't set bounding box
        super().__init__(bounding_margin_width_factor=Solver.NO_BOUNDING_BOX)

    def _solve(self):
        """
        The base solver returns for each robot a simple path of its start and end position -
        which for most scenes might not be valid!

        :return: path collection of motion planning
        :rtype: :class:`~discopygal.solvers_infra.PathCollection`
        """
        path_collection = PathCollection()
        for robot in self.scene.robots:
            if type(robot) is RobotRod:
                start_location = robot.start[0]
                start_data = {'angle': robot.start[1]}
                end_location = robot.end[0]
                end_data = {'angle': robot.end[1]}
            else:
                start_location = robot.start
                start_data = {}
                end_location = robot.end
                end_data = {}
            start_point = PathPoint(start_location, start_data)
            end_point = PathPoint(end_location, end_data)
            path = Path([start_point, end_point])
            path_collection.add_robot_path(robot, path)
        return path_collection

    @classmethod
    def get_arguments(cls):
        return {}

3.1.3. Random Solver

This is an example for a solver that creates randomized paths by picking randomized valid points in the scene, creating a graph from them by picking random connections (the roadmap) and then searching for the shortest path for each robot (from it’s start point to it’s end point) Of course this also isn’t a good solver that produces valid paths (check with the ‘Verify paths’ button) but it is possible to draw the paths and run the animation

Solver Class code

RandomSolver.py

import random
import networkx as nx

from discopygal.solvers_infra import Robot, Path, PathPoint, PathCollection
from discopygal.solvers_infra.Solver import Solver
from discopygal.geometry_utils.bounding_boxes import calc_scene_bounding_box
from discopygal.geometry_utils.collision_detection import ObjectCollisionDetection
from discopygal.bindings import FT, Point_2


class RandomSolver(Solver):
    def __init__(self, num_landmarks, num_connections):
        super().__init__()
        # Initializing properties of solver
        self.num_landmarks = num_landmarks
        self.num_connections = num_connections

        self._collision_detection = {}
        self._start = None
        self._end = None
        self._roadmap = None

    def _sample_random_point(self):
        # Randomize a point inside the boundaries of the scene
        x = random.uniform(self._x_min, self._x_max)
        y = random.uniform(self._y_min, self._y_max)
        return Point_2(FT(x), FT(y))

    def _create_random_point(self, robots):
        point = self._sample_random_point()

        # Set a point that for all robots it won't collide with an obstacle
        is_valid_point = False
        while not is_valid_point:
            point = self._sample_random_point()
            is_valid_point = all([self._collision_detection[robot].is_point_valid(point) for robot in robots])

        return point

    def _create_random_roadmap(self, robots):
        roadmap = nx.Graph()
        # Add random points
        for _ in range(self.num_landmarks):
            point = self._create_random_point(robots)
            roadmap.add_node(point)

        # Add random connections
        for _ in range(self.num_connections):
            v, u = random.sample(list(roadmap.nodes), 2)
            roadmap.add_edge(v, u, weight=1)

        for robot in robots:
            # Add starting point of robot to the graph
            roadmap.add_node(robot.start)

            # Connect start to a random point
            roadmap.add_edge(robot.start, *random.sample(list(roadmap.nodes), 1), weight=1)

            # Add ending point of robot to the graph
            roadmap.add_node(robot.end)

            # Connect to end to a random point
            roadmap.add_edge(robot.end, *random.sample(list(roadmap.nodes), 1), weight=1)

        return roadmap


    def load_scene(self, scene):
        super().load_scene(scene)
        self._x_min, self._x_max, self._y_min, self._y_max = calc_scene_bounding_box(self.scene)

        # Build collision detection for each robot
        for robot in self.scene.robots:
            self._collision_detection[robot] = ObjectCollisionDetection(scene.obstacles, robot)

    def get_graph(self):
        return self._roadmap

    def _solve(self):
        self.log("Solving...")
        self._roadmap = self._create_random_roadmap(self.scene.robots)

        path_collection = PathCollection() # Initialize PathCollection (stores the path for each robot)
        for i, robot in enumerate(self.scene.robots):
            self.log(f"Robot {i}")

            # Check if there is a possible path for the robot in the graph
            if not nx.algorithms.has_path(self._roadmap, robot.start, robot.end):
                self.log(f"No path found for robot {i}")
                return PathCollection()

            # Get the shortest path for the robot
            found_path = nx.algorithms.shortest_path(self._roadmap, robot.start, robot.end)
            points = [PathPoint(point) for point in found_path] # Convert all points to PathPoints (to make a path out of them)
            path = Path(points) # Make a path from all PathPoints
            path_collection.add_robot_path(robot, path) # Add the current path for the current robot to the path collection

        return path_collection

    @classmethod
    def get_arguments(cls):
        # Returns the configurable properties of the solver (presented in gui)
        # in format of: 'property_name': (Description, Default value, Type)
        return {
            'num_landmarks': ('Number of points', 5, int),
            'num_connections': ('Number of connections', 5, int),
        }

Use solver in script

random_solver_example.py

from discopygal.solvers_infra import Scene
from discopygal.solvers_infra.verify_paths import verify_paths
from discopygal_tools.solver_viewer import start_gui

from RandomSolver import RandomSolver

# Load scene from file
scene = Scene.from_file('basic_scene.json')

# "Solve" the scene (find paths for the robots)
solver = RandomSolver(num_landmarks=10, num_connections=10)

# Option 1 - give scene to solve (load + solve)
path_collection = solver.solve(scene)  # Returns a PathCollection object

# Option 2 - First load scene and then solve it (solves the last loaded scene)
solver.load_scene(scene)
path_collection = solver.solve()
path_collection = solver.solve()  # Solves again the loaded scene

# Print the points of the paths
for i, (robot, path) in enumerate(path_collection.paths.items()):
    print("Path for robot {}:".format(i))
    for j, point in enumerate(path.points):
        print(f'\t Point {j:2}:  ', point.location)  # point is of type PathPoint, point.location is CGALPY.Ker.Point_2
    print()

result, reason = verify_paths(scene, path_collection)
print(f"Are paths valid: {result}\t{reason}")

# Optional - Open solver_viewer with our solver and scene

# Option 1 - Use solve object we made:
print("First gui")
start_gui(scene, solver)

# Option 2 - Use solver's class type to create a new one:
print("Second gui")
start_gui(scene, RandomSolver)

# Option 3 - Use solver's class name to create a new one (must pass solver's module):
print("Third gui")
start_gui(scene, "RandomSolver", "RandomSolver.py")

# Option 4 - Passing the path to the scene json file
print("Fourth gui")
start_gui("basic_scene.json", solver)

Invoke Solver viewer with solver from command line

solver_viewer -sl RandomSolver -sf RandomSolver.py -sc simple_motion_planning_scene.json

4. Creating a scene

Another main issue is to create a scene.
There are two ways to do this, the first is to create a json file interactively with Scene designer and load it and the second is to directly to create a discopygal.solvers_infra.Scene object during the script and use it (as was shown in the example).
Check the discopygal.solvers_infra.Scene class documentation to be familiar with the available methods and options.

5. Discopygal starter

Discopygal starter is exactly the same to the regular discopygal except it doesn’t contain any pre-written solver.
All other usage and tools are the same.
It has the basic abstract Solver class and it is required to implement by yourself solvers that will inherit from this class.
If using discopygal-starter and discopygal make sure to install them in two different virtual envs or otherwise uninstall the first before installing the second version.