Tensor Roadmap Solver

Tensor Roadmap

class discopygal.solvers_infra.tensor_solver.tensor_roadmap.TensorRoadmap(roadmaps, scene, nearest_neighbors_class, metric, sampler)

A class that represents a tensor roadmap, which couples a roadmap of each robot (which was built separately) into one large graph product representing motion of all the robots. Note that since for most (nontrivial) cases the explicit roadmap is intractable, we generate an interface which allows us to query the tensor roadmap without explicitly building it - and also remembering the subgraph of queries we made.

Graphs are represented using networkx. Vertices of a roadmap of a single robot are Point_2, while vertices of the tensor roadmap are of type Point_d.

Parameters:

  • roadmaps (dict<Robot, Roadmap>) – a mapping between each robot and its roadmap

  • scene (Scene) – scene to solve

  • nearest_neighbors_class (NearestNeighbors) – a nearest neighbors algorithm class.

  • metric (Sampler) – a metric for choosing best edge, can be different then the nearest_neighbors metric!

  • metric – a sampler to use for sampling points

clean_tensor_edge(p, q)

Get a tensor edge (made of tensor vertices p and q) and clean it, i.e. make sure that no two robots are intersecting each other. If two robots intersect - then make sure one of them stays in place.

Parameters:
Returns:

q’, a vertex for which (p,q’) is a valid motion

Return type:

Point_d

connect_to_roadmap(new_vertex, prev_vertex)

Disconnects previous connection

find_best_edge(tensor_vertex, tensor_point)

Given a vertex in the tensor graph and a random tensor point, choose an edge in the tensor graph that is made of the edges in the original roadmaps that take us the closest to the tensor point.

Also note that if two robots collide, we try to make one of them to stay in place (i.e. some robots might stay in place, but at least one robot is guaranteed to move - if an edge was added).

Returns:

True if an edge was added

Return type:

bool

get_tensor_subgraph()

Get the subgraph of the tensor roadmap discovered so far

nearest_tensor_vertex(tensor_point)

Get a tensor point and return a tensor vertex (i.e. vertex of hat(V), the vertices of the tensor graph) that is the closest when comparing in the high dimensional space.

Parameters:

tensor_point (Point_d) – a point in the high dimensional space

try_connecting(vertex1, vertex2)

Try connecting two vertices of the tensor graph. We do that by the method proposed by de Berg: http://www.roboticsproceedings.org/rss05/p18.html (Finding each path individually and then trying to find a prioritization which is collision free). Return True if we succeeded connecting.

Parameters:

  • vertex1 (Point_d) – first vertex in the tensor roadmap

  • vertex2 – second vertex in the tensor roadmap

Returns:

True if we connected the vertices

Return type:

bool

Tensor Solver

class discopygal.solvers_infra.tensor_solver.tensor_solver.TensorSolver(**kwargs)

Bases: SamplingSolver

Base solver class for solvers that use a tensor roadmap - constructs a two-dimensional roadmap for each robot and searches on the tensor product of these roadmaps.

build_roadmap()

Constructs the roadmap of points in the configuration space which a path will be searched on to find a solution. Every sampling solver should implement how to build the roadmap.

Returns:

The built roadmap. Each node represents a point in configuration space (dimension = 2*robots_num)

Return type:

Roadmap

abstract build_robot_roadmap(robot)

Creates a two-dimensional roadmap for the given robot

Parameters:

robot (Robot) – The robot o build a roadmap for

Returns:

The roadmap

Return type:

Roadmap

search_path_on_roadmap()

After already constructed a roadmap, plan a path for each robot (i.e. return paths for all the robots) If failed to find a path for each robot return an empty PathCollection (PathCollection())

The search method of the basic class SamplingSolver is simply finding the shortest path according to the weights of the edges (the weight attribute should be called weight)

Returns:

Path collection of motion planning (path for each robot)

Return type:

PathCollection

abstract search_tensor_roadmap()

Search method the explore the tensor roadmap a find a solution path on it