Problem Statement
In non-mathematical language: we have the borders, same or none walls, a starting
point and ending point. The question is; how to draw a discrete curve from starting
point to ending point without cross the walls and be inside of boarders. In this work we focus to
find this curve regardless of the shortest route. Generally our goal is to go around of walls and be
inside in borders.
Indoor route example.
In mathematical language: we have two coordinates $P_{0}$, $P_{1}$ in $\Re^{2}$ and set
of constraints $r$ with goal to model an objective function $G$ in $R^{nx2}$ with $n$ the density of
discrete curve, with $G_{0} = P_{0}$ and rest $G_{i}$ with $0 < i < n$ is computed by
the objective function. Optimizing the following objectives:
optimize:
-
square distance error minimization of $P_{1}$, $G_{n}$ and
-
constraints error minimization for each $G_{i}$. Constraints are effected by
geometry. For example if geometry is a circle then the error is euclidean, another
examples is if the geometry is an orthogonal rectangle then the error is maximum
value of absolute distance between center and coordinates per diminution. Minkowski
distance is the general approach:
$$
dist_{p}(x, y) = {(\sum_{i=0}^{d} {| {x_{i} - y_{i}} |}^{p})}^{\frac{1}{p}}, \, p > 0
$$
$$
\lim_{p \rightarrow \infty} dist_{p}(x, y) = \max_{i=0}^{d}| {x_{i} - y_{i}} |
$$
Also, we use a constant $λ$ to regularize the distance between
the constraint critical line and a coordinate $G_{i}$. This constant as increases we have
less regularization, if $λ$ equals with $0$ we have no regularization:
$$
BE_{λ}(dist_{p}(\frac{x}{v}, \frac{m}{v})) = 0,
$$
$$
BE_{λ}(x) =
\begin{cases}
1 - e^{-{x}^{λ}} & if λ > 0 \\
\max(x - 1, 0) & if λ = 0
\end{cases}
$$
$$
WE_{λ}(dist_{p}(\frac{x}{v}, \frac{m}{v})) = 0,
$$
$$
WE_{λ}(x) =
\begin{cases}
e^{-{x}^{λ}} & if λ > 0 \\
\max(1- x, 0) & if λ = 0
\end{cases}
$$
Example of border and two types of walls. The first wall (left one) has geometry where $p \rightarrow \infty$
and the second wall (right one) has geometry where $p = 2$. $m, v$ are the center of geometric object and variance respectively.
Also, we illustrate $λ$ regularization constant as an area line.
System Architecture
First the system gets the set coordinates, the staring and the ending coordinates $P_{start}, P_{end}$ as inputs.
Giving as output a sequence of vectors as discrete curve $G$ through nonlinear function $Ω$. In the
second phase, $G$ go through Error functions, getting the total cost. Using this cost to tune the variables of
$Ω$ to minimize the errors.
Objective Function
The main issue to model the Objective Function $G$ is the non-linearity and how to adapt it to
optimize our problem.
| Properties |
Model Base |
Definitions |
| Transform the coordinate space to transition feature space. |
$t = P^{T} \hat{*} w + b$ |
-
$\hat{*}$: upscale convolution operator
-
$w$: orientation convention kernel,
-
$b$: transition vector.
|
| Transform the transition feature space to pseudo high dimensional space. |
$h = H(t)$ |
$H$: pseudo high dimensional transformation function |
| Transform the pseudo high dimensional space to transition space. |
$Ω = h * w + b$ |
$*$: convolution operator |
With the above properties we show the following $Ω$ transition matrix model:
First we transpose $P$ coordinates to feature, next go through Coordinate to transition feature space
(C2Tf), a Stack of Upscale 1D Convolutional Neural Network (U1DCNN). In second phase go through Pseudo High Denominational
space with $n$ number of feature elements (Tf2H), a Neural network Layer (U1DCNN, 1D CNN or PFC). In final phase go through
High dimensional space to Transition space (H2T), a Stack of 1D Convolutional Neural Network (1DCNN) & Parallel Full Connected Layer (PFC).
After the PFC we get as output $Ω$ transitions.
$G$ is a product of $Ω$ matrix, with $n$ $ω_{i}$ transition vectors. Every $G_i$ is the previous one
plus the transition vector.
$$
G_0 = P_{0},
$$
$$
G_i = G_{i -1} + ω_{i-1}.
$$
We use CNNs as filters to mix the features by kernel. As results a smoother curve.
Cost Function
After the objective function we need to define the constraints errors. In this work we use the
geometry of Minkowski distance where $p$ tents to be infinity:
$$
b_i = BE_{λ}(dist_{p}(\frac{G_{i}}{v^{b}}, \frac{m^{b}}{v^{b}}))
$$
$$
w_i = WE_{λ}(dist_{p}(\frac{G_{i}}{v^{w}}, \frac{m^{w}}{v^{w}}))
$$
Having constraints errors and objective function, we create a cost function which is minimized
with global minimum $0$:
$$
C = \sum_{k=0}^{d}(P_{end}^{k} - G_{n}^{k})^2 + \sum_{i=1}^{n -1}(b_i + w_i)
$$
Optimization
Minimizing the cost $C$ with the use Adam, a back-propagation method. Back-propagation is an optimization
process through iterations try to find a noiseless minimum. At variable initialization step we generate
by normal distribution. Also, we use a score based on Accuracy score which count the number of $G_{i}$
which satisfy the constraints.
Back Propagation is an iteration method which in every iteration change the variables (aka weights)
by compute the gradient of cost function over weight. After that update weights with following method:
$$
w_{new} := w_{old} - a \frac{\partial C}{\partial w_{old}},
$$
with $0 < a < 1$ is constant (aka learning rate) which contribute to reduce the phenomenon of explode gradient.