Broaden scope of FrontierModel to include current search tree

[robfitzgerald]

Our current trait representing the frontier model is:

pub trait FrontierModel: Send + Sync {
    fn valid_frontier(
        &self,
        edge: &Edge,
        state: &[StateVar],
        previous_edge: Option<&Edge>,
    ) -> Result<bool, FrontierModelError>;
}

optionally providing the previous edge in this scope allows us to restrict access to the next edge in specific applications such as no left turn intersections, but, falls short of allowing us to restrict based on more complex maneuvers that extend beyond 2 edges.

in order to address this, we could replace the previous_edge with the tree:

pub trait FrontierModel: Send + Sync {
    fn valid_frontier(
        &self,
        edge: &Edge,
        state: &[StateVar],
        tree: &HashMap<VertexId, SearchTreeBranch>,
        direction: &Direction
    ) -> Result<bool, FrontierModelError>;
}

Some implications of this change:

• the direction must also be provided, in the case that the tree is used by a reverse search in a bi-directional algorithm
• the previous edge can be found by performing a single iteration of backtracking, an O(1) cost

[robfitzgerald]

While writing this issue, I had the thought that we could make this change everywhere that we are passing a previous edge. Maybe that would make everything a little more concise, and broaden the scope of access modeling too, in case that is helpful.

[nreinicke]

While writing this issue, I had the thought that we could make this change everywhere that we are passing a previous edge. Maybe that would make everything a little more concise, and broaden the scope of access modeling too, in case that is helpful.

yeah that would make sense to me and doesn't come at any cost (I think) since we're just passing a reference around

[kylecarow]

@robfitzgerald I see the addition of _state_model: &StateModel to the signature in 244338d and am trying to understand it, are you able to clarify this for me?

[robfitzgerald]

sure thing. the state: &[StateVar] represents the state of a search, where, at each index, we store some value such as distance, time, energy, etc. RouteE Compass was designed so that future devs could develop their own TraversalModels, FrontierModels, and CostModels, which could interact with these vectors. but problems begin if one has a different idea of which index relates to which type of feature.

enter the StateModel. that is new as of last week. it is created when we instantiate a SearchInstance for an algorithm, and it provides an API for interacting with state vectors (&[StateVar]) by feature name, including any unit conversions and even custom unit types.

i think there aren't any FrontierModels that need to use the state model (in this repository, at least), so, you can likely just ignore it for the work you are doing. let me know if i'm wrong about that, glad to talk through the API + any changes you need to make.