Core Types

Graph

GraphUtils.AbstractCustomNGraphType
abstract type AbstractCustomNGraph{G,N,ID} <: AbstractCustomGraph

An abstract Custom Graph type, with an underlying graph of type G, nodes of type N with ids of type ID. All concrete subtypes CG<:AbstractCustomNGraph must implement the following methods: get_graph(g::CG),get_vtx_ids(g::CG), get_vtx_map(g::CG), and get_nodes(g::CG). These methods are implemented by default if g::CG has the following fields:

  • graph ::CG
  • nodes ::Vector{N}
  • vtx_map ::Dict{ID,Int}
  • vtx_ids ::Vector{ID}

Abstract subtypes of AbstractCustomNGraph{G,N,ID} include:

  • AbstractCustomNEGraph{G,N,E,ID} - a graph with custom edges of type E
source
GraphUtils.get_vtx_mapFunction
get_vtx_map(g::AbstractCustomNGraph{G,N,ID})

return a data structure (e.g, a 'Dict{ID,Int}') mapping node id to node index.

source
GraphUtils.node_valFunction
node_val(node)

Return the value associated with a node. Part of the optional node interface for nodes in an AbstractCustomNGraph.

source
GraphUtils.edge_valFunction
edge_val(edge)

Returns the value associated with an edge. Part of the optional interface for edges in an AbstractCustomNEGraph.

source
GraphUtils.edge_sourceFunction
edge_source(edge)

Returns the ID of the source node of an edge. Part of the required interface for edges in an AbstractCustomNEGraph.

source
GraphUtils.edge_targetFunction
edge_target(edge)

Returns the ID of the target node of an edge. Part of the required interface for edges in an AbstractCustomNEGraph.

source
GraphUtils.replace_node!Function
replace_node!(g::AbstractCustomNGraph{G,N,ID},node::N,id::ID) where {G,N,ID}

Replace the current node associated with id with the new node node.

source
GraphUtils.add_node!Function
add_node!(g::AbstractCustomNGraph{G,N,ID},node::N,id::ID) where {G,N,ID}

Add node to g with associated id.

source
GraphUtils.make_nodeFunction
make_node(g::AbstractCustomNGraph{G,N,ID},val,id)

Construct a node of type N from val and id. This method must be implemented for whatever custom node type is used.

source
GraphUtils.make_edgeFunction
make_edge(g::G,u,v,val) where {G}

Construct an edge u → v of type _edge_type(g) based on val. Default behavior is to throw an error.

source
GraphUtils.add_child!Function
function add_child!(graph,parent,node,id)

add node child to graph with id id, then add edge parentchild

source
GraphUtils.add_parent!Function
function add_parent!(graph,child,parent,id)

add node parent to graph with id id, then add edge parentchild

source
GraphUtils.rem_node!Function
rem_node!

removes a node (by id) from g. Note about LightGraphs.rem_vertex!: "internally the removal is performed swapping the vertices v and nv(G), and removing the last vertex nv(G) from the graph"

source
GraphUtils.topological_sortFunction
topological_sort(G)

Returns a topological sort of the vertices of a graph, with the property that v1 < v2 iff there is not forward path through the graph from v2 to v1. G must be non-cyclic. Can handle disjoint graphs.

source

Tree

GraphUtils.validate_treeFunction
validate_tree(n::AbstractTreeNode)

Ensure that the transform tree is in fact a tree–no cycles, and no duplicate ids

source
GraphUtils.validate_embedded_treeFunction
validate_embedded_tree(graph,f=v->get_node(graph,v))

Verify that all graph edges are mirrored by the parent-child structure stored in the nodes.

source

Factory World

GraphUtils.construct_vtx_mapFunction
construct_vtx_map(vtxs,dims)

Returns a matrix M such that MV[i,j] == v, where v is the index of the vertex whose coordinates are (i,j)

Arguments:

  • vtxs : a list of integer coordinates
  • dims : the dimensions of the grid
source
GraphUtils.construct_edge_cacheFunction
construct_edge_cache(vtxs,vtx_map)

Returns a cache such that cache[v] = {(0,1),(0,0),...}, the set of all valid directions in which a robot may move from vertex v.

Arguments:

  • vtxs : a list of integer coordinates
  • vtxmap : a matrix such that `vtxmap[i,j] = v, wherevtxs[i,j] = v`.
source
GraphUtils.construct_expanded_zonesFunction
construct_expanded_zones(vtxs,vtx_map,pickup_zones,dropoff_zones;
    shapes=[(1,1),(1,2),(2,1),(2,2)])

A utility for constructing drop-off/pick-up zones where large-footprint objects need to be delivered. Returns a dictionary mapping vertices to a dict of shape=>vtxs for expanded size delivery zones. For each starting vertex, the expanded zone is selected as the appropriately sized region that overlaps with the original vertex, does not overlap with any obstacles, and has minimal overlap with all other vertices in the zone list.

Arguments:

  • vtxs : a list of integer coordinates
  • vtxmap : a matrix such that `vtxmap[i,j] == v, wherevtxs[v] == (i,j)`
  • zones : a list of integer vertex indices identifying the zones to be expanded
source
GraphUtils.validate_expanded_zonesFunction
validate_expanded_zones(vtx_map,expanded_zones)

Verify that all vertices of each expanded zone do not overlap with obstacle regions, and that each expanded zone contains the original vertex.

source
GraphUtils.SparseDistanceMatrixType
SparseDistanceMatrix{G,M}

Stores a graph and sparse distance matrix. When the distance matrix is queried for the distance between start and goal, it first checks that this distance has been computed. If not, it will first compute the distances from all nodes to goal before returning the queried distance.

source
GraphUtils.remap_idxFunction
remap_idx(m::SparseDistanceMatrix,v,config)

Maps an index and configuration from the base grid to the transformed grid represented by m.graph. config represents the position of the query pt relative to the coordinates that correspond to v.

source
GraphUtils.config_index_to_tupleFunction
config_index_to_tuple(shape::Tuple{Int,Int}, idx::Int)

Convert a config index to a tuple coordinate representation. Assumes the following layout for config indices given shape (m,n): 1 2 ... n ____________________________ 1 | 1 2 ... n 2 | n+1 n+2 ... 2n ... | m | (m-1)n+1 (m-1)n+2 ... m*n

source
GraphUtils.RemappedDistanceMatrixType
RemappedDistanceMatrix

Stores a distance matrix that corresponds to a "shifted" grid graph with a new configuration space layered over a base graph. The shape m.s of m::RemappedDistanceMatrix defines the convolution kernel used to generate the modified.

source
GraphUtils.construct_regular_factory_worldFunction
construct_regular_factory_world()

Returns a GridFactoryEnvironment with regularly spaced obstacle regions surrounded by alternating pick-up and drop-off locations.

Keyword Arguments:

  • nobstaclesx = 2 : number of obstacles in x direction
  • nobstaclesy = 2 : number of obstacles in y direction
  • obs_width = [2;2] : obstacle width in both directions
  • obs_offset = [1;1] : width of buffer region around each obstacle
  • env_pad = [1;1] : env pad
  • env_scale = 0.5 : determines the width of each grid cell when the coordinates of the environment are transformed to continuous Cartesian space.
  • transition_time = 2.0 : determines the nominal travel time for a robot to move from one grid cell to an adjacent one.
source
GraphUtils.construct_factory_env_from_vtx_gridFunction
construct_factory_env_from_vtx_grid(vtx_grid;kwargs...)

Arguments:

  • vtxgrid : a matrix such that `vtxgrid[i,j] > 0` represents free space, otherwise an obstacle.

Keyword Arguments:

  • cell_width = 0.5 : determines the width of each grid cell when the coordinates of the environment are transformed to continuous Cartesian space.
  • transition_time = 2.0 : determines the nominal travel time for a robot to move from one grid cell to an adjacent one.
  • pickup_zones = Int[] : a list of vertices that represent pick-up points
  • dropoff_zones = Int[] : a list of vertices that represent drop-off points
source