API Reference

abstract type AbstractCustomNEGraph{G,N,E,ID} <: AbstractCustomNGraph{G,N,ID}

An abstract Custom Graph type, with an underlying graph of type G, nodes of type N with ids of type ID, and edges of type E. All concrete subtypes CG<:AbstractCustomNEGraph must implement the required AbstractCustomNGraph interface in addition to the following methods:

• out_edges(g::CG) : returns an integer-indexed forward adjacency list fadj such that fadj[u::Int][v::Int] contains the custom edge associated with u → v.
• in_edges(g::CG) : returns an integer-indexed backward adjacency list badj such that badj[v::Int][u::Int] contains the custom edge associated with u → v.

The above methods are implemented by default if g::CG has the following fields:

• outedges ::Vector{Dict{Int,E}}
• inedges ::Vector{Dict{Int,E}}

AgentID

Special helper for identifying agents.

CachedElement{E}

A mutable container for caching things.

CachedTreeNode{ID} <: AbstractTreeNode{ID}

Abstract type representing a node with a cached value. Concrete subtypes have a cached element (accessed via cached_element(n)).

specify tangents explicitly

CustomEdge{E,ID}

A custom node type. Fields:

• id::ID
• val::E

CustomNEGraph{G,N,E,ID}

Custom graph type with custom edge and node types.

CustomNETree{G,N,E,ID}

Custom tree type with custom edge and node types.

CustomGraph

An example concrete subtype of AbstractCustomNGraph.

CustomNTree

An example concrete subtype of AbstractCustomNTree.

CustomNode{N,ID}

A custom node type. Fields:

• id::ID
• val::N

DistMatrixMap

Maps team size to the effective distance (computed by Djikstra) between leader (top left) vtxs. A DistMatrixMap is constructed by starting with a base environment grid graph, which is represented as a binary occupancy grid. The occupancy grid is then convolved with kernels of various sizes (which represent configurations of robots moving as a team). The output of each convolution represents a new occupancy grid corresponding to the workspace of the robot team. It is assumed that the "lead" robot is always in the top left of the configuration. If a team of robots wishes to query the distance to a particular target configuration, they pass the leader's current vtx, the leader's target vtx, and the team configuration (shape) to the DistMatrixMap, which returns the correct distance.

IndicatorGrid

A matrix such that M[i,j] == 0 indicates "free" and M[i,j] == 1 indicates "obstacle".

struct TemplatedID{T} <: AbstractID

A simple way to dispatch by Node type.

VtxGrid

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

VtxID

Special helper for identifying schedule vertices.

Base.copy(e::CachedElement)

Shares the e.element, since it doesn't need to be replaced until set_element! is called. Copies e.is_up_to_date to preserve the cache state.

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

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

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

Add node to g with associated id.

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

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

backup_descendants(g::AbstractCustomNGraph{G,N,ID},template)

Return a dictionary mapping each node's id to the id of it's closest descendant matching template.

cached_element(n::CachedTreeNode)   = n.element

Default method for retrieving the cached element of n.

cached_node_up_to_date(n::CachedTreeNode)

Check if n is up to date.

capture_connected_nodes(G,vtxs,f)

Collect the connected set of nodes in G that intersects with vtxs and such that f(v) == true for each v in the set. Args:

• vtxs::Union{Int,Vector{Int},Set{Int}}

clip(a,b,c)

Returns the closest element to a on the interval [b,c]

collect_ancestors(graph,v) = collect_subtree(graph,v,:in)

collect_descendants(graph,v) = collect_subtree(graph,v,:out)

collect_subtree(graph,v,dir=:out)

Return a set of all nodes in the subtree of graph starting from v in direction dir.

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

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

construct_factory_env_from_indicator_grid

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

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_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_vtx_grid

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_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

contract_by_node_type(g,f)

Constructs a new graph of the same type as g, whose nodes are formed by those for which f(n) == true. Edges are contracted so that, e.g. n1 => n2 => n3 => n4 collapses to n1 => n4 if f(n1) && !(f(n2)) && !(f(n3)) && f(n4).

convolve_with_occupancy_kernel(indicator_grid::IndicatorGrid,kernel)

Construct a new indicator grid corresponding to convolution of the original grid with a kernel. The second argument may be a Matrix{Int} or a Tuple{Int,Int} indicating the size for a ones() kernel.

curve_turn_rate(S::ParametricSpline,t::Real)

computes the turn rate (w.r.t. t) of the tangent vector to a curve.

depth_first_search(graph,v,goal_function,expand_function,
	neighbor_function=outneighbors)

Returns the first vertex satisfying goalfunction(graph,v). Only expands v if expandfunction(graph,v) == true.

depth_first_search(node::AbstractTreeNode,goal_function,expand_function,
	neighbor_function=outneighbors)

Returns the first vertex satisfying goalfunction(graph,v). Only expands v if expandfunction(graph,v) == true.

dfs_check_cycle(graph,v,neighbor_func=inneighbors)

Check if graph contains a cycle with v in it

draw_random_elements(vec,n)

Draw n elements uniformly at random (without replacement) from vec.

edge_cover(G,vtxs,mode=:all)

Get all edges coming from vertices vtxs. If mode=:in, just collect incoming edges. If :out, just outgoing. If :all, both.

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.

edge_val(edge)

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

eligible_predecessors(node)

Identifies the types (and how many) of eligible predecessors to node Return type: Dict{DataType,Int}

eligible_successors(node)

Identifies the types (and how many) of eligible successors to node Return type: Dict{DataType,Int}

exclusive_edge_cover(G,vtxs,mode)

Returns the edge cover, minus all edges whose sources and edges are both contained within vtxs.

filtered_topological_sort(graph,template)

Iterator over nodes that match template.

find_index_in_sorted_array(array, x)

Assumes that array is already sorted. Returns index at which x would need to be inserted in order to maintain ordering of array. Chooses the smallest index in the case of a tie.

Looks like "Base.searchsorted" does the same thing as this.

get_all_root_nodes

get_all_terminal_nodes

get_biggest_tree(graph,dir=:in)

Return the root/terminal vertex corresponding to the root of the largest tree in the graph.

get_cached_value!(n::CachedTreeNode)

Return the up to date cached value of n. This triggers a reach back to parent nodes if necessary.

get_dist_matrix(G)

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

get_distance(mtx_map::DistMatrixMap,v1::Int,v2::Int,shape::Tuple{Int,Int}=(1,1),config_idx=1)

Returns the length of the minimum distance collision-free path between vertices v1 and v2 for an object of footprint shape.

Arguments:

• mtx_map : a DistMatrixMap
• v1 : an integer corresponding to the source vertex in the graph
• v2 : an integer corresponding to the destination vertex in the graph
• shape : the footprint of the object that will move between v1 and v2
• config_idx : an integer that identifies the position of the reference point within the footprint.

get_element(n::CachedElement)

Retrieve the element stored in n.

get_files_matching(base_path,ext,keywords=[])

Get all files in a directory that match the extension ext, and (optionally) which contain any of keywords

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

return the underlying graph of type G.

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

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

get_root_node(n::AbstractTreeNode{E,ID}) where {E,ID}

Return the root node of a tree

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.

global_verbosity()

Query the global verbosity setting (VERBOSITY::Int)

has_ancestor(node::AbstractTreeNode,other::AbstractTreeNode)

Check if other is an ancestor of node.

has_descendant(node::AbstractTreeNode,other::AbstractTreeNode)

Check if other is a descendant of node.

has_path(graph,v,v2)

Return true if graph has a path from v to v2

in_edges(g::AbstractCustomNEGraph{G,N,E,ID})

Returns an integer-indexed backward adjacency list badj (e.g., badj::Vector{Dict{Int,E}}) such that badj[v::Int][u::Int] contains the custom edge associated with u → v.

initialize_dense_vtx_grid

Returns a grid graph that represents a 2D environment with regularly spaced
rectangular obstacles

Returns a grid graph that represents a 2D environment with obstacles placed
over specific vertices

Returns a grid graph that represents a 2D environment with regularly spaced
rectangular obstacles

Returns a grid that represents a 2D environment with regularly spaced
rectangular obstacles.

Indicator grid values:
    0 == FREE
    1 == OCCUPIED

initialize_vtx_grid_from_indicator_grid()

Args: * grid: an indicator grid, where grid[i,j] == 0 denotes that cell (i,j) is free, and grid[i,j] != 0 denotes that the cell is impassable.

Returns: * A matrix whose non-zero elements represent the ids of vertices in a graph embedded in the 2D grid.

insert_to_sorted_array!(array, x)

Assumes that array is already sorted. Inserts new element x so that array remains sorted. Requires that Base.isless(a::C,b::C) where C==typeof(x) be implemented.

intersections_between_circles(v1,v2,r1,r2)

isroot_node(G,v)

Inputs: G - graph v - query vertex

Outputs: returns true if vertex v has no outneighbors

is_up_to_date(n::CachedElement)

Check if the n is up to date.

linear_interpolation

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.

matches_keywords(p,keywords)

Check if any of the keywords occurs in p.

matches_template(template,node)

Checks if a candidate node satisfies the criteria encoded by template.

nested_default_dict_get(dict,k,keylist...;default=nothing)

Query into an arbitrarily deep nested dict until finding a non-dict value or returning default when the current key does not point to a dict. Example

dict = Dict()
nested_default_dict_set!(dict,1,2,"val")
nested_default_dict_set!(dict,1,2,3,"other val")
nested_default_dict_get(dict,1,2) == "val"
nested_default_dict_get(dict,1,2,3) == "val"

nested_default_dict_set!(dict,keylist...,[val])

Sets the value of a nested dictionary, indexed by a list of keys, to val. If the full keylist does not yet exist, create the intermediate dicts along the way. Example:

dict = Dict()
nested_default_dict_set!(dict,1,2,3,"my val")

node_id(node)

Return the id of a node. Part of the required node interface for nodes in an AbstractCustomNGraph.

node_iterator(graph,it)

Wraps an iterator over ids or vertices to return the corresponding node at each iteration.

node_val(node)

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

num_eligible_predecessors(node)

Returns the total number of eligible predecessors to node.

num_eligible_successors(node)

Returns the total number of eligible successors to node.

num_required_predecessors(node)

Returns the total number of required predecessors to node.

num_required_successors(node)

Returns the total number of required successors to node.

one_hot(::Type{T},n::Int,i::Int) where {T}

Returns a Vector{T} of length n such that v[i] == 1 and v[j] .== 0 for all j != i.

out_edges(g::AbstractCustomNEGraph{G,N,E,ID})

Returns an integer-indexed forward adjacency list fadj (e.g., fadj::Vector{Dict{Int,E}}) such that fadj[u::Int][v::Int] contains the custom edge associated with u → v.

helper to pad a matrix with some value around the edges

propagate_backward!(child::CachedTreeNode,parent::CachedTreeNode,args...)

Propagate information from child to parent.

propagate_backward!(n::CachedTreeNode,args...)

Propagate information up the tree from n.

propagate_forward!(parent::CachedTreeNode,child::CachedTreeNode,args...)

Propagate information from parent to child.

propagate_forward!(n::CachedTreeNode,args...)

Propagate information down the tree from n.

read_env(io)

Loads saved environment from a .toml file.

recompute_cached_distances!

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

redirect_to_files(dofunc, outfile, errfile)

redirects output of stdout and stderr to outfile and errfile, respectively. Usage:

redirect_to_files(prefix * ".log", prefix * ".err") do
    compute(...)
end

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"

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.

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.

required_predecessors(node)

Identifies the types (and how many) of required predecessors to node Return type: Dict{DataType,Int}

required_successors(node)

Identifies the types (and how many) of required successors to node Return type: Dict{DataType,Int}

resample array

set_cached_node_up_to_date!(n::CachedTreeNode,val=true)

Set "up to date" status of n to val.

set_element!(n::CachedElement,g)

Set the element stored in n. Does NOT set the is_up_to_date flag.

set_global_verbosity!(val::Int)

Set the global verbosity to val

set_time_stamp!(n::CachedElement,t=time())

Set the time stamp of n.

set_up_to_date!(n::CachedElement,val::Bool=true)

Set the time stamp of n.

sprint_padded(i,pad=3,leftaligned=false)

Pads the string representation of i

sprintpaddedlist(vec,pad=3,leftaligned=false)

Returns a string as in: julia> sprint_padded_list([1,2,3],3) "[ 1 2 3]"

swap_with_end_and_delete!(vec,v)

Replaces vec[v] with last(vec), then removes the last element from vec

tangent_rate(S::ParametricSpline,t::Real)

Computes the rate (w.r.t. t) at which the tangent vector to a curve is changing.

time_stamp(n::CachedElement)

Return the time_stamp at which n was last modified.

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.

transform_iter(f, it) = Base.Iterators.accumulate((a,b)->f(b), it)

Transform iterator that applies f to each element of it.

transplant!(graph,old_graph,id)

Share node with id in old_graph to graph with the same id.

update_element!(n::CachedTreeNode,element,args...)

Update cached element of n, and propagate relevant information forward and backward via propagate_forward! and propagate_backward!

update_element!(n::CachedElement,g)

Set the element of n to g, update the is_up_to_date flag and the time stamp.

validate_edge_cache(G,vtxs,cache)

Verifies that for a graph G embedded in space such that vertex v has coordinates vtxs[v], every edge v₁ → v₂ is stored in the edge cache. In other words, for every edge v₁ → v₂, the unit direction vector obtained by vtxs[v₂] - vtxs[v₁] is a member of cache[v₁].

Arguments:

• G : a graph on which the functions vertices and outneighbors can be called
• vtxs : a list of integer coordinates
• cache : an edge cache such that e.g. cache[v] = {(0,1),(0,0),...}, the set of all valid directions in which a robot may move from vertex v

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.

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.

validate_tree(n::AbstractTreeNode)

Ensure that the subtree of n is in fact a tree–no cycles, and no duplicate ids

validate_tree(n::AbstractTreeNode)

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

wrap_get

Index into array a by first wrapping the indices idx.

wrap_idx(n,idx)

Wrap index to a one-dimensional array of length n

wrap_to_pi(θ₀)

wraps the angle θ₀ to a value in (-π,π]

@log_info

A helper macro for printing at various verbosity levels. Usage: @log_info(limit::Int,level::Int,msg...) @log_info(limit::Int,solver,msg...) Args:

• limit::Int - logging threshold
• level::Int - the verbosity level
• msg... - message to print if level > limit