Core Types

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

get_graph(g::AbstractCustomNGraph{G,N,ID})

return the underlying graph of type G.

get_vtx_ids(g::AbstractCustomNGraph{G,N,ID})

return the vector Vector{ID} of g's unique vertex ids.

get_vtx_map(g::AbstractCustomNGraph{G,N,ID})

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

get_nodes(g::AbstractCustomNGraph{G,N,ID})

Return the vector Vector{N} of g's nodes.

node_val(node)

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

edge_val(edge)

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

edge_source(edge)

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

edge_target(edge)

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

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.

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

Add node to g with associated id.

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.

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.

function add_child!(graph,parent,node,id)

add node child to graph with id id, then add edge parent → child

function add_parent!(graph,child,parent,id)

add node parent to graph with id id, then add edge parent → child

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"

isroot_node(G,v)

Inputs: G - graph v - query vertex

Outputs: returns true if vertex v has no outneighbors

get_all_root_nodes

get_all_terminal_nodes

get_dist_matrix(G)

Get the distance matrix corresponding to the edge weights of a graph

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.

abstract type AbstractCustomNTree{N,ID} <: AbstractCustomNDiGraph{N,ID}

Abstract custom graph type with tree edge structure.

abstract type AbstractTreeNode{E,ID}

E is element type, ID is id type

validate_tree(n::AbstractTreeNode)

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

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.

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

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`.

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

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.

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.

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.

recompute_cached_distances!

Recompute all cached distances (important if, e.g., the graph has been modified)

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

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.

GridFactoryEnvironment

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.

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

construct_factory_env_from_indicator_grid

Args: * grid: an indicator grid whose zero entries denote free space (non-zero denotes obstacle)