Skip to main content

Traversal

Each running dynamic map in the agent provides graph traversal services as shown in the live data viewer image below.

findNearestNeighbor​

Request​

  • startNodeId: The ID of the node from which to start the search.
  • neighbors: A list of node IDs. The nearest node from this list to the startNodeId is returned.
  • edgeType: The edge types the process is allowed to use for graph traversal. If not provided, the traversal will be unrestricted.
  • nodeType: The node types the process is allowed to use for graph traversal. If not provided, the traversal will be unrestricted.
  • nodeData: A boolean value that specifies whether the node data should be included in the response. The default is false.

Response​

The nearest neighbor to the startNodeId from the list of neighbors is returned. An example response is shown in the image below. Here the traversal has been set up to only traverse between bd.spot.waypoint.v1 nodes and only along bd.spot.traversable.v1 edges.

lookupTransform​

Request​

  • parentId: The ID of the parent node.
  • childId: The ID of the child node.

Response​

The transform from the parentId to the childId is returned. An example of this is shown in the image below:

sortByShortestPath​

The sortByShortestPath service returns an approximate shortest path traversing from a start node to a list of visit nodes. It does this by first solving the Travelling Salesman Problem (TSP) using a simple Nearest Neighbor approach. If refinement is enabled, the path is then refined using an approach called Simulated Annealing.

Request​

  • startNodeId: The ID of the node from which to start the search.
  • visitNodeIds: A list of node IDs to visit.
  • edgeType: The edge types the process is allowed to use for graph traversal. If not provided, the traversal will be unrestricted.
  • nodeType: The node types the process is allowed to use for graph traversal. If not provided, the traversal will be unrestricted.
  • nodeData: A boolean value that specifies whether the node data should be included in the response. The default is false.
  • refinement: A boolean value that specifies whether the path should be refined. The default is false. Refinement settings are outlined here: Path Refinement.

Response​

  • An object containing:
    • path: The approximate shortest path traversing from startNodeId to all visitNodeIds is returned. An example of this is shown in the image below.
    • refinement: If the refinement parameter is set to true, the refinement results are provided.

Path Refinement with Simulated Annealing​

The sort by shortest path service returns an approximate solution to the Travelling Salesman Problem (TSP). By providing only an approximate solution, a response to this service can be returned in a reasonable amount of time, even for large maps. Simulated Annealing is used to refine the initial solution created from the simple Nearest Neighbor approach.

Simulated Annealing involves iteratively swapping two edges in the path. If the new path is shorter, we accept this solution and continue. If the new path is longer, we accept it with a probability that decreases over time. This allows the algorithm to escape local minima and potentially find a better solution as the algorithm progresses.

The probability of accepting a worse solution is given by the following equation:

P=ecurrentPathLength−proposedNewPathLengthTP = e^{\frac{\text{currentPathLength} - \text{proposedNewPathLength}}{T}}

Where TT is the temperature of the system. The temperature is decreased by a cooling rate with each accepted path.

The sort by shortest path service provides the following parameters to control the refinement process as shown in the image above.

  • refinement: A boolean value that specifies whether the path should be refined. The default is false.
  • startTemperature: The initial temperature of the system. The default is 10000.
  • exitTemperature: The temperature at which the system should stop refining. The default is 0.1.
  • coolingRate: The rate at which the temperature decreases. The default is 0.999.
  • maxIterations: The maximum number of iterations to refine the path. The default is 5000.
  • convergenceIterations: If the path has not improved by the convergenceThreshold for convergenceIterations, the refinement process will stop. The default is 10 iterations.
  • convergenceThreshold: The threshold at which we consider a solution to be converged. The default is 1 (meter).