### robotics代写|寻路算法代写Path Planning Algorithms|Visibility-Based Optimal Path Planning

statistics-lab™ 为您的留学生涯保驾护航 在代写寻路算法Path Planning Algorithms方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写寻路算法Path Planning Algorithms代写方面经验极为丰富，各种代写寻路算法Path Planning Algorithms相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## robotics代写|寻路算法代写Path Planning Algorithms|Existence of Solutions

First, we consider Problem 4.1. The following result ensures that the set of all admissible paths $\Gamma$ satisfying condition (1) is nonempty.

Proposition 4.1 Under the conditions of Theorem 3.3, there exists an admissible path $\Gamma \in \Omega$ that satisfies condition (4.2).

Proof 4.I From Theorem $3.3$, there exists a finite point set $P^{(N)}=\left{x^{(k)}, k=\right.$ $1, \ldots, N} \subset \Omega$ that satisfies the total visibility constraint (1). If the specified end points $x_{o}$ and $x_{f} \in P^{(N)}$, then under the assumption that $\Omega$ is simply connected, it is always possible to construct a path $\Gamma$ in $\Omega$ corresponding to a Jordan arc passing through all the points in $P^{(N)}$. In particular, if the line segment joining any pair of points in $P^{(N)}$ lies in $\Omega$, then a Jordan arc composed of straightline segments joining the successive points in $P^{(N)}$ can always be constructed. A trivial case is where $\Omega$ is a compact convex subset of $\mathbb{R}^{2}$. If $x_{o}$ and/or $x_{f} \notin P^{(N)}$, we augment $P^{(N)}$ by these points, and proceed with the construction of a Jordan arc. Finally, from the constructed $\Gamma$, the corresponding path $\Gamma_{\mathcal{P}}$ in $\mathcal{P}$ can be determined from ${(x, g(x)): x \in \Gamma} .$

Remark 4.3 Proposition $4.1$ implies the existence of a Jordan arc passing through a finite set of observation points $\left(x^{(k)}, f_{h_{v}}\left(x^{(k)}\right)\right) \in G_{f_{b_{E}}}$ such that $G_{f}$ is totally visible. In general, the set of observation points for total visibility is not unique. Moreover, the cardinality of this set depends on $f$.

Remark 4.4 Suppose that the line segment $L$ joining the points $x_{o}$ and $x_{f}$ lies in $\Omega$, and $\bigcup_{x \in L} \mathcal{V}\left(\left(x, f_{h_{E}}(x)\right)\right)=G_{f}$, then $L$ is an optimal path. If $\bigcup_{x \in L} \mathcal{V}\left(\left(x, f_{h_{v}}(x)\right)\right) \subset$ $G_{f}$, then for a certain class of $G_{f}$, the optimal path $\Gamma^{*}$ is close to $L$ in the sense of arc length. Minimal excursions from $L$ can be introduced so that the invisible part $G_{f}-\bigcup_{x \in L} \mathcal{V}\left(\left(x, f_{h_{v}}(x)\right)\right)$ becomes visible.

For Problem 4.1″, we first construct the set $\tilde{\Omega} \stackrel{\text { def }}{=}\left{x \in \Omega:|\nabla f(x)| \leq f_{\max }^{\prime}\right}$, and then find the shortest admissible path $\Gamma^{} \subset \bar{\Omega}$ such that $\bigcup_{x \in \Gamma^{}} \mathcal{V}\left(\left(x, f_{h_{v}}(x)\right)\right)=$ $G_{f}$. In general, it is possible that $\bar{\Omega}$ consists of disjoint subsets of $\Omega$, and there may not exist admissible paths in $\bar{\Omega}$ (e.g. $x_{o}$ and $x_{f}$ lie in two disjoint subsets of $\Omega$ separated by a strip on which $|\nabla f(x)|>f_{\max }^{\prime}$ for all points $x$ on this strip). Consequently, Problem 4.1″ has no solution. Note also that the line segment $L$ joining $x_{o}$ and $x_{f}$ may not lie in $\bar{\Omega}$.

Since $f$ is a $C_{1}$-function, the set $\bar{\Omega}$ is compact. Assuming the existence of an admissible path in $\bar{\Omega}$, the observations given in Remarks $4.3$ and $4.4$ are also applicable to this case.

## robotics代写|寻路算法代写Path Planning Algorithms|Optimality Conditions

Here, we develop optimality conditions for Problem $4.1$ under the assumption that a solution exists. From Theorem $3.3$, there exists a finite point set $P^{(N)}=\left{x^{(k)}, k=\right.$ $1, \ldots, N} \subset \Omega$ with $x^{(1)}=x_{o}$ and $x^{(N)}=x_{f}$ such that
$$\bigcup_{k=1}^{N} \mathcal{V}\left(\left(x^{(k)}, f_{h_{v}}\left(x^{(k)}\right)\right)\right)=G_{f}$$
is satisfied. Let $P$ denote the set of all such $P^{(N)}$ ‘s with $2 \leq N<\infty$. The cardinality of $P$ is generally infinite. Now, for a given $P^{(N)} \subset P$, let $\tilde{\mathcal{A}}{P(N)}$ denote the set of all admissible paths $\Gamma$ formed by line segments joining distinct pairs of points in $P^{(N)}$. The cardinality of $\overline{\mathcal{A}}{P(N)}$ is $\leq(N-2)$ !. Thus, Problem $4.1$ reduces to finding a finite point set $P^{(N)} \subset P$ and an admissible path $\Gamma \in \tilde{\mathcal{A}}{P(N)}$ such that the arc length $$\Lambda(\Gamma)=\sum{k=1}^{N-1}\left|x^{(k+1)}-x^{(k)}\right|$$
is minimized. For convenience, the points $x^{(k)}, k=2, \ldots, N-1$ are indexed consecutively along the path $\Gamma$ initiating from $x_{o}$ and moving towards the end point $x_{f}$.
The following simple necessary condition for optimality can be deduced readily from the definition of arc length:

Proposition $4.2$ Let $\Gamma^{}$ be an optimal admissible path for Problem 4.1, and $P^{\left(N^{}\right)}=$ $\left{x_{}^{(k)} \in \Gamma^{}, k=1, \ldots, N^{}\right}$ be a finite point set satisfying (4.16). Then, for any perturbed admissible path $\Gamma \in \overline{\mathcal{A}}{\bar{P}^{\left(N^{}\right)}}$ with finite point set $\left{x{}^{(1)}, \ldots, x_{}^{(k-1)}, x_{}^{(k)}+\right.$ $\left.\delta x, x_{}^{(k+1)}, \ldots, x_{}^{\left(N^{}\right)}\right}$ in which the point perturbation $\delta x$ about $x_{}^{(k)}$ satisfies $x_{}^{(k)}+$ $\delta x \in \Omega$, and condition (4.16) holds, the following inequality:

\begin{aligned} &\left|x_{}^{(k)}+\delta x-x_{}^{(k-1)}\right|+\left|x_{}^{(k+1)}-x_{}^{(k)}-\delta x\right| \geq\left|x_{}^{(k+1)}-x_{}^{(k)}\right| \ &\quad+\left|x_{}^{(k)}-x_{}^{(k-1)}\right|, \quad k=2, \ldots, N^{}-1, \end{aligned} must be satisfied. For Problem 4.2, a necessary condition for optimality can be derived by considering local path perturbations. Let $I=[0,1]$. First, we parameterize an admissible path $\Gamma$ by the scalar parameter $\lambda \in I$, i.e. $$\Gamma=\left{\left(x_{1}, x_{2}\right) \in \Omega: x_{1}=q_{1}(\lambda), x_{2}=q_{2}(\lambda), \lambda \in I\right}$$ where $q_{1}$ and $q_{2}$ are real-valued $C_{1}$-functions on $I$ satisfying $$\left(q_{1}(0), q_{2}(0)\right)=\left(x_{o 1}, x_{o 2}\right) \text { and }\left(q_{1}(1), q_{2}(1)\right)=\left(x_{f 1}, x_{f 2}\right)$$ Let $\Gamma^{}$ and $\Gamma$ denote an optimal path and an admissible perturbed path specified by $q^{}(\lambda)=\left(q_{1}^{}(\lambda), q_{2}^{}(\lambda)\right)$ and $q^{}(\lambda)+\eta(\lambda)=\left(q_{1}^{}(\lambda)+\eta_{1}(\lambda), q_{2}^{}(\lambda)+\eta_{2}(\lambda)\right), \quad \lambda \in I$,
respectively, where $\eta=\left(\eta_{1}, \eta_{2}\right) \in \Sigma_{\Gamma^{}}$, the set of all admissible path perturbations about $\Gamma^{}$ defined by $\Sigma_{\Gamma^{}}=\left{\eta \in C_{1}\left(I ; \mathbb{R}^{2}\right): \eta(0)=(0,0), \eta(1)=(0,0) ; q^{}(\lambda)+\right.$ $\eta(\lambda) \in \Omega$ for all $\lambda \in I}$, with $C_{1}\left(I ; \mathbb{R}^{2}\right)$ being the normed linear space of all continuous functions defined on $I$ with their values in $\mathbb{R}^{2}$ and having continuous first derivatives on $I$, and normed by: $|\eta|_{m}=\sum_{i=1,2}\left(\max {\lambda \in I}\left|\eta{i}(\lambda)\right|+\max {\lambda \in I}\left|\eta{i}^{\prime}(\lambda)\right|\right)$, where $(\cdot)^{\prime}$ denotes differentiation with respect to $\lambda$.

## robotics代写|寻路算法代写Path Planning Algorithms|Numerical Algorithms

To facilitate the development of numerical algorithms for the optimal path planning problems, a mesh on $\Omega$ using standard methods such as Delaunay triangulation is established. Then $G_{f}$ is approximated by a polyhedral surface $\hat{G}{f}$, in particular, a surface formed by triangular patches. In practical situations, the function $f=f(x)$ is usually given in the form of numerical data. An approximation of $G{f}$ can be obtained by interpolation of the given numerical data. Here, algorithms are developed for the approximate Problems $4.1$ and $4.2$ that make use of the numerical data directly.
For the Shortest Path Problem 4.1, consider the simplest case where the line segment $L$ joining the end points $x_{o}$ and $x_{f}$ lies in $\Omega$. Remark $4.4$ suggests that a possible approach to obtaining a solution to the approximate Problem $4.1$ is to seek first a finite number of points along $L$ having maximal visibility, and then introduce additional points close to $L$ to achieve total visibility. Finally, a Jordan-arc with minimal length passing through all the observation points is constructed.

Suppose that on $\Omega$, a mesh consisting of points $x^{(k)}, k=1, \ldots, M$ along with the approximate surface $\hat{G}{f}$ formed by triangular patches have been established. For convenience, let $x^{(1)}=x{o}$ and $x^{(M)}=x_{f}$. Let $\hat{\mathcal{G}}$ denote the set of all Jordan arcs connecting $x^{(1)}$ and $x^{(M)}$ formed by line segments corresponding to the edges of the triangles. The basic steps in our algorithm for determining an optimal path for the approximate Problem $4.1$ without assuming that the line segment $L$ joining $x_{o}$ and $x_{f}$ lies in $\Omega$ are as follows:

Step 3 Determine $\hat{\mathcal{G}}^{}=\left{\Gamma_{j}^{}, j=1, \ldots, K\right}$, the set of all Jordan arcs in $\hat{\mathcal{G}}$ having the shortest path length.
Step 4 Select a path in $\hat{\mathcal{G}}^{}$, say $\Gamma_{i}^{}$.
Step 5 Compute the visible set $\mathcal{V}\left(\left(x^{(k)}, f_{h_{v}}\left(x^{(k)}\right)\right)\right)$ corresponding to each point $x^{(k)}$ along the path $\Gamma_{i}^{}$ and its projection $\Pi_{\Omega} \mathcal{V}\left(\left(x^{(k)}, f_{h_{v}}\left(x^{(k)}\right)\right)\right)$. Step 6 Determine whether there exists a combination of points $x^{(k)}$ along $\Gamma_{i}^{}$ such that the union of their visible sets $\mathcal{V}\left(\left(x^{(k)}, f_{h_{v}}\left(x^{(k)}\right)\right)\right)$ is equal to $G_{f}$.
If YES, then $\Gamma_{i}^{}$ is an optimal path for the approximate Problem 4.1, STOP; if NO, select a neighboring path of $\Gamma_{i}^{}$ in the sense of arc length, and GO TO Step $5 .$

Remark $4.5$ In Steps 2 and 3, instead of considering triangles in $\Omega$, we may consider triangular patches associated with the polyhedral approximation of the surface $G_{f}$. Efficient algorithms for computing the shortest arc length such as those due to Sharir and Shorr [3], O’Rourke et al. [4], and Lawler [5] may be used.

Remark $4.6$ Step 5 involves the computation of visible sets $\mathcal{V}\left(\left(x^{(k)}, f_{h_{x}}\left(x^{(k)}\right)\right)\right)$ associated with points $x^{(k)}$ along the path $\Gamma_{i}^{*}$, an NP-hard problem in computational geometry. This task can be accomplished using a suitable algorithm developed recently by Balmes and Wang [1]. The complexity of that algorithm is $O\left(n p^{2}\right)$, where $n$ and $p$ are the number of observation points and the number of triangular patches respectively. This algorithm can be easily modified to take into account the limited aperture of cameras or sensors.

## robotics代写|寻路算法代写Path Planning Algorithms|Optimality Conditions

⋃ķ=1ñ在((X(ķ),FH在(X(ķ))))=GF

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。