Utils

QuadraticStateControlFunction{T, MT<:AbstractMatrix{T}}

Quadratic function on state and input defined as x'Qx + u'Ru + 2x'Nu + 2x'q + 2u'r + v

Yield the nodes reachable from this node.

Return the cost of a solution path that arrives at state2 from state1 via action, assuming cost c to get up to state1. If the problem is such that the path doesn't matter, this function will only look at state2. If the path does matter, it will consider c and maybe state1 and action. The default method costs 1 for every step in the path.

Search the shallowest nodes in the search tree first.

Search the deepest nodes in the search tree first.

Search the nodes with the lowest f scores first. You specify the function f(node) that you want to minimize; for example, if f is a heuristic estimate to the goal, then we have greedy best first search; if f is node.depth then we have depth-first search.

Create a list of nodes from the root to this node.

Create a list of nodes from the root to this node.

AbstractQueue is an abstract type. There are three types: MyStack(): A Last In First Out Queue. FIFOQueue(): A First In First Out Queue. MyPriorityQueue(f,ext): Queue where items are sorted by f, (default <). Each type supports the following methods and functions: append!(q,item) – add an item to the queue extend!(q,items) – equivalent to: for item in items: append(q,item) pop!(q) – return the top item from the queue length(q) – number of items in q

Return an empty list, suitable as a Last-In-First-Out Queue.

Search through the successors of a problem to find a goal. The argument fringe should be an empty queue. Don't worry about repeated paths to a state.

Return True if the state is a goal. The default method compares the state to P.goal, as specified in the constructor. Implement this method if checking against a single goal is not enough.

A* search is best-first graph search with f(n) = g(n)+h(n). You need to specify the h function when you call astar_search.

A* search is best-first graph search with f(n) = g(n)+h(n). You need to specify the h function when you call astar_search.

Search the shallowest nodes in the search tree first.

Search through the successors of a problem to find a goal. The argument fringe should be an empty queue. If two paths reach a state, only use the best one.

Search the nodes with the lowest f scores first. You specify the function f(node) that you want to minimize; for example, if f is a heuristic estimate to the goal, then we have greedy best first search; if f is node.depth then we have depth-first search.

Given a state, return a sequence of (action, state) pairs reachable from this state. If there are many successors, consider an iterator that yields the successors one at a time, rather than building them all at once.

A node in a search tree. Contains a pointer to the parent (the node that this is a successor of) and to the actual state for this node. Note that if a state is arrived at by two paths, then there are two nodes with the same state. Also includes the action that got us to this state, and the total pathcost (also known as g) to reach the node. Other functions may add an f and h value; see bestfirstgraphsearch and astar_search for an explanation of how the f and h values are handled.

Search the deepest nodes in the search tree first.

A queue in which the minimum (or maximum) element (as determined by f) is returned first. Keys of type T and priorities of type V.

A First-In-First-Out Queue.

SearchProblem

Fields

- `initial`  -- initial state of type `S` or a list of initial state of type `S`.
- `goal`     -- possibly a goal state of type 'Union{Nothing,S}''.

Example

struct Problem{S} <: SearchProblem{S}
    initial::Union{S,Vector{S}}
    goal::Union{Nothing,S}
end
The constructor specifies the initial state, and possibly a goal
state, if there is a unique goal.
function Problem(initial::S; goal=nothing) where S
    return Problem{S}(initial,goal)
end

Abstract_BB_Problem #abstract branch and bound problem

Sould implement the methods below

get_min_bounding_box(elli, optimizer)

Finds the minimum bounding box containing the ellipsoid {(x-c)'P(x-c) < 1}.

cost: cost to reach its parent

Return a list with all the children of node

Basic generic RRT algorihtm
SI : initial state (this will be the root of the tree) ;
SF : target state that we try to reach ;
distance : function that defines a metric between the states ;
rand_state : function that returns a random candidate state ;
new_conf : function that returns a reachable state, with the action and the cost ;
keep : function to filter the node that we want to add during an iteration;
stop_crit : stop criteria ;
RRTstar : boolean to use RRT* ;
compute_transition : to compute transition between to given state (if RRTstar is true).

add a node as a leave

assuming that the path_cost of a node has changed (and its depth), we should propagate the new cost to its children

return the path from node to the root of the tree

Tree structure with

• cost for transitions (the cost function a non-negative function);
• an underlying metric between the states that are encapsulated in the nodes of the tree