solver

Documentation

Overview

Package solver solves a 2D linear programming problem in 2D ambient space.

Index

• func Solve(m M, cs []constraint.C, o O, v vector.V) (vector.V, feasibility.F)
• type M
• type O

Functions

func Solve

func Solve(m M, cs []constraint.C, o O, v vector.V) (vector.V, feasibility.F)

Solve attempts to calculate a solution to the linear programming problem which satisifes all input constraints and maximizes / minimizes the given input optimization function. Solve will return infeasible if there is no such solution.

Solve takes as input a set of bounding constraints as defined by de Berg (2008), a set of 2D linear constraints, a (potentially non-linear) optimization function, and an initial solution.

The order by which constraints are given to this function does not matter; we are adding the constraints iteratively, and refining our solution similar to the simplex approach, though applied to a non-linear constraint due to the distance optimization target.

This is analogous to Agent.linearProgram2 in the official RVO2 implementation.

N.B.: The initial solution is the base case from de Berg, i.e. a known optimal solution which satisfies the bounding constraints. For linear optimization functions, this is the v0 defined in Algorithm 2DBoundedLP of de Berg.

Types

type M

type M interface {
	// Bound calculates the segment of intersection between the bounding
	// constraint and any additional linear constraint. If the binding
	// constraint is linear, the returned segment may be half-infinite.
	//
	// Bound must return false if the input constraint lies outside the
	// bounds of M.
	Bound(c c2d.C) (segment.S, bool)

	// In checks if the given vector satisifies the initial bounds of M.
	In(v vector.V) bool
}

M is an additional (potential non-linear) constraint which clamps the solution a minimum and maximum value. This corresponds to the bounded constraints defined in de Berg et al. (2008). Note that while de Berg assumes all constraints are linear, we relax this assumption slightly and effectively allow specifying per-constraint bounds.

This is useful for e.g. when the bounded constraint is circular, as in the case of solving an LP problem in velocity-space with a maximum speed constraint. We can model the circular constraint as a series of linear constraints which lie tangent to the circle-constraint intersection. To make this slightly more efficient, we can instead just truncate the intersection of each "real" constraint to be fully bounded by the circle-constraint intersection.

type O

type O func(s segment.S) vector.V

O specifies an optimization function for the 2D lineaer problem. This function assumes there a single optimal value found over the span of the segment. Note that the function may not be linear -- this is a relaxation on the general LP problem.

For example, we may use the distance function as a optimization function, even though the function itself is not of degree 1, because the distance function has a single root.