Reference

Construction

robotsp.construct.from_coordinate_list(coordinates, distfn=None, args=(), weight='weight')[source]

Construct a nx.Graph using the input coordinates

Parameters:
  • coordinates (list) – The input coordinates
  • distfn (Callable, optional) – The function to be used to compute the distance/weight between nodes. If None, robotsp.metric.euclidean_fn() will be used.
  • args (tuple, optional) – Additional arguments to be passed to the distfn
  • weight (str, optional) – Use this edge attribute as the edge weight
Returns:

rotated – The rotated tour
Return type:

list
robotsp.construct.from_setslist(setslist, distfn, args=(), weight='weight')[source]
robotsp.construct.from_sorted_setslist(setslist, distfn, args=(), weight='weight', verbose=False)[source]

Metrics

robotsp.metric.birrt_shortcut_traj_duration(qstart, qgoal, robot, max_iters, max_ppiters, try_swap=False)[source]
robotsp.metric.cubic_traj_duration(qa, qb, robot)[source]
robotsp.metric.euclidean_fn(x, y, weights=None)[source]
robotsp.metric.euclidean_fn_int(x, y, weights=None, mult_factor=1000)[source]
robotsp.metric.geo_fn(x, y)[source]
robotsp.metric.linear_traj_duration(qa, qb, robot)[source]
robotsp.metric.manhattan_fn(x, y, weights=None)[source]
robotsp.metric.max_joint_diff_fn(x, y, weights=None)[source]
robotsp.metric.parabolic_traj_duration(qa, qb, robot)[source]
robotsp.metric.retimed_traj_duration(qa, qb, robot, method)[source]

Parser

class robotsp.parser.SUPPORTED_PROBLEM_TYPES[source]

Bases: enum.Enum

GTSP = <SUPPORTED_PROBLEM_TYPES.GTSP: 2>
TOUR = <SUPPORTED_PROBLEM_TYPES.TOUR: 3>
TSP = <SUPPORTED_PROBLEM_TYPES.TSP: 1>
class robotsp.parser.SUPPORTED_WEIGHT_FORMATS[source]

Bases: enum.Enum

FULL_MATRIX = <SUPPORTED_WEIGHT_FORMATS.FULL_MATRIX: 2>
LOWER_DIAG_ROW = <SUPPORTED_WEIGHT_FORMATS.LOWER_DIAG_ROW: 1>
class robotsp.parser.SUPPORTED_WEIGHT_TYPES[source]

Bases: enum.Enum

EUC_2D = <SUPPORTED_WEIGHT_TYPES.EUC_2D: 2>
EXPLICIT = <SUPPORTED_WEIGHT_TYPES.EXPLICIT: 4>
GEO = <SUPPORTED_WEIGHT_TYPES.GEO: 3>
MAN_2D = <SUPPORTED_WEIGHT_TYPES.MAN_2D: 1>
robotsp.parser.fn_euc_2d(x, y)[source]
robotsp.parser.fn_man_2d(x, y)[source]
robotsp.parser.get_keyword_index(lines, keyword)[source]
robotsp.parser.read_tsplib(filename)[source]
robotsp.parser.tsplib_to_dict(filename)[source]
robotsp.parser.write_gtsplib(filename, graph, sets, params)[source]

Solvers

class robotsp.solver.SolverParameters[source]

Bases: object

initialized()[source]
robotsp.solver.compute_cspace_trajectories(robot, cgraph, ctour, params)[source]
robotsp.solver.compute_execution_time(trajectories)[source]
robotsp.solver.compute_robot_configurations(robot, targets, params, qstart=None)[source]
robotsp.solver.generate_gtsp_graph(robot, targets, params)[source]
robotsp.solver.glkh_solver(robot, targets, params, path='~/.ros', cache=None)[source]
robotsp.solver.robotsp_solver(robot, targets, params)[source]
Parameters:
  • robot (orpy.robot) – OpenRAVE robot
  • targets (list) – List of rays (orpy.Ray)
robotsp.solver.tsp_cspace_solver(robot, targets, params)[source]

Traveling Salesman Problem

robotsp.tsp.compute_tour_cost(graph, tour, weight='weight', is_cycle=True)[source]
robotsp.tsp.nearest_neighbor(graph, restarts=10, weight='weight')[source]

Recursive Nearest-Neighbor algorithm to solve the traveling salesman problem.

These are the steps of the algorithm for each restart:

  1. Start on a random node as current node;
  2. Find the shortest edge connecting the current node with an unvisited node;
  3. Mark the found node as current and visited;
  4. Go to step 2 until all nodes are visited
Parameters:
  • graph (NetworkX graph) –
  • restarts (int, optional (default=10)) – Number of times the algorithm will try a different, randomly selected, node as starting point
  • weight (string, optional (default='weight')) – Edge data key corresponding to the edge weight
Returns:

best_tour – The sequence for visiting all the nodes
Return type:

list
robotsp.tsp.rotate_tour(tour, start=0)[source]

Rotate a tour so that it starts at the given start index. This is equivalent to rotate the input list to the left.

Parameters:
  • tour (list) – The input tour
  • start (int, optional (default=0)) – New start index for the tour
Returns:

rotated – The rotated tour
Return type:

list
robotsp.tsp.scip_solver(graph, weight='weight')[source]
robotsp.tsp.two_opt(graph, weight='weight')[source]