Nearly time-optimal paths for a ground vehicle

It is well known that the sufiqdent family of time-optimal paths for both Dubins‘ as well as Reeds-Shepp‘ s car models consist of the concatenation of circular arcs with nrtximum curvature and straight line segments, all tangentially connected.These time-optimal solutions suffer from some drawbacks. Their discontinuous curvature profile, together with the wear and impairment on the control equipment that the bang-bang solutions induce, calls for “smoother” and more supple reference paths to follow. Avoiding the bang-bang solutions also raises the robttstness with respect to any possible uncertainties. In this paper, ourmain tool for generating these “nearly firne-optunal”, but nevertheless continuous-curvature paths, is to use the Pontryagin Maximum Principle (PMP) and make an appropriate and cmming choice of the Lagrangmn function. Despite some rewarding sinmlation results, this concept turns out to be numerically divergent at some instances. Upon a more careful investigation, it can be concluded that the problem at hand is nearly singular. This is seen by applying the PMP to Dubins‘ car and studymg the corresponding two point boundary value problem, which turn out to be singular. Realizing this, one is able to contradict the widespread behef that all the information about the motion of a mobile platform lies in the initial values of the attxiliary variables associated with the PMP.     

On minimum-time paths of bounded curvature with position-dependent constraints

We consider the problem of a particle traveling from an initial configuration to a final configuration (given by a point in the plane along with a prescribed velocity vector) in minimum time with non-homogeneous velocity and with constraints on the minimum turning radius of the particle over multiple regions of the state space. Necessary conditions for optimality of these paths are derived to characterize the nature of optimal paths, both when the particle is inside a region and when it crosses boundaries between neighboring regions. These conditions are used to characterize families of optimal and nonoptimal paths. Among the optimality conditions, we derive a “refraction” law at the boundary of the regions that generalizes the so-called Snell’s law of refraction in optics to the case of paths with bounded curvature. Tools employed to deduce our results include recent principles of optimality for hybrid systems. A numerical example is given to demonstrate the derived results.     

Minimum-link paths among obstacles in the plane

Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(E(n) log² n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and (n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst).Joseph Mitchell was partially supported by NSF Grants IRI-8710858 and ECSE-8857642, and by a grant from Hughes Research Laboratories. This work was begun while Günter Rote and Gerhard Woeginger were at the Freie Universität Berlin, Fachbereich Mathematik, Institut für Informatik, and it was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM). Gerhard Woeginger acknowledges the support by the Fonds zur Förderung der Wissenschaftlichen Forschung, Projekt S32/01.     

Shortest noncrossing paths in plane graphs

Let G be an undirected plane graph with nonnegative edge length, and letk terminal pairs lie on two specified face boundaries. This paper presents an algorithm for findingk noncrossing paths inG, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in timeO(n logn) wheren is the number of vertices inG andk is an arbitrary integer.     

Optimization-based path planning framework for industrial manufacturing processes with complex continuous paths

The complexity of robotic path planning problems in industrial manufacturing increases significantly with the current trends of product individualization and flexible production systems. In many industrial processes, a robotic tool has to follow a desired manufacturing path most accurately, while certain deviations, also called process tolerances and process windows, are allowed. In this work, a path planning framework is proposed, which systematically incorporates all process degrees of freedom (DoF), tolerances and redundant DoF of the considered manufacturing process as well as collision avoidance. Based on the specified process DoF and tolerances, the objective function and the hard and soft constraints of the underlying optimization problem can be easily parametrized to find the optimal joint-space path. By providing the analytical gradients of the objective function and the constraints and utilizing modern multi-core CPUs, the computation performance can be significantly improved. The proposed path planning framework is demonstrated for an experimental drawing process and a simulated spraying process. The planner is able to solve complex planning tasks of continuous manufacturing paths by systematically exploiting the process DoF and tolerances while allowing to move through singular configurations, which leads to solutions that cannot be found by state-of-the-art concepts.     

复杂网络中最短路径问题的求解算法研究

本文以时间代价作为目标函数,针对复杂网络的优化问题进行研究,给出了目标评价函数模型的建立过程,提出了改进的A＊算法求解复杂网络中最短路径问题的算法,并以城市交通为例,对算法进行了验证,实验结果表明所提出的算法可适用于一般多重图中最短路径问题的快速求解,具有广泛的应用价值。     

GIS-T中途经多地点后返回的最短路径搜索算法

在交通运输过程中，用户经常需要搜索经过多个无序地点后返回起点的最短路径。为此，首先在GIS-T中原有空间数据的基础上，动态地建立了一个两点间最短路径信息库；然后，给出了一个不依赖搜索图、结合路线特点的算法，实现了对所需的最短路径的搜索。     

Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor

We consider a two-edge connected, undirected graph G=(V,E)$G=(V,E)$, with n$n$ nodes and m$m$ non-negatively real weighted edges, and a single source shortest paths tree (SPT) T$T$ of G$G$ rooted at an arbitrary node r$r$. If an edge in T$T$ is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge  , instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog²n)$O\left(m{log}^{2}n\right)$ time and O(m)$O\left(m\right)$ space algorithm to find a best swap edge for every edge of T$T$, thus improving for m=o(n²/log²n)$m=o(n^2/{log}^{2}n)$ the previously known O(n²)$O\left(n^2\right)$ time and space complexity algorithm.     

A harmonic potential field approach for joint planning and control of a rigid,separable nonholonomic,mobile robot

The main objective of this paper is to provide a tool for performing path planning at the servo-level of a mobile robot. The ability to perform, in a provably-correct manner, such a complex task at the servo-level can lead to a large increase in the speed of operation, low energy consumption and high quality of response. Planning has been traditionally limited to the high level controller of a robot. The guidance velocity signal from this stage is usually converted to a control signal using what is known as an electronic speed controller (ESC). This paper demonstrates the ability of the harmonic potential field (HPF) approach to generate a provably-correct, constrained, well-behaved trajectory and control signal for a rigid, nonholonomic robot in a stationary, cluttered environment. It is shown that the HPF-based, servo-level planner can address a large number of challenges facing planning in a realistic situation. The suggested approach migrates the rich and provably-correct properties of the solution trajectories from an HPF planner to those of the robot. This is achieved using a synchronizing control signal whose aim is to align the velocity of the robot in its local coordinates, with that of the gradient of the HPF. The link between the two is made possible by representing the robot using what the paper terms “separable form”. The context-sensitive and goal-oriented control signal used to steer the robot is demonstrated to be well-behaved and robust in the presence of actuator noise, saturation and uncertainty in the parameters. The approach is developed, proofs of correctness are provided and the capabilities of the scheme are demonstrated using simulation results.     

Decomposition principle in model predictive control for linear systems with bounded disturbances

Considering a constrained linear system with bounded disturbances, this paper proposes a novel approach which aims at enlarging the domain of attraction by combining a set-based MPC approach with a decomposition principle. The idea of the paper is to extend the “pre-stabilizing” MPC, where the MPC control sequence is parameterized as perturbations to a given pre-stabilizing feedback gain, to the case where the pre-stabilizing feedback law is given as the linear combination of a set of feedback gains. This procedure leads to a relatively large terminal set and consequently a large domain of attraction even when using short prediction horizons. As time evolves, by minimizing the nominal performance index, the resulting controller reaches the desired optimal controller with a good asymptotic performance. Compared to the standard “pre-stabilizing” MPC, it combines the advantages of having a flexible choice of feedback gains, a large domain of attraction and a good asymptotic behavior.     

Optimality of affine control system of several species in competition on a sequential batch reactor

In this paper, we analyse the optimality of affine control system of several species in competition for a single substrate on a sequential batch reactor, with the objective being to reach a given (low) level of the substrate. We allow controls to be bounded measurable functions of time plus possible impulses. A suitable modification of the dynamics leads to a slightly different optimal control problem, without impulsive controls, for which we apply different optimality conditions derived from Pontryagin principle and the Hamilton–Jacobi–Bellman equation. We thus characterise the singular trajectories of our problem as the extremal trajectories keeping the substrate at a constant level. We also establish conditions for which an immediate one impulse (IOI) strategy is optimal. Some numerical experiences are then included in order to illustrate our study and show that those conditions are also necessary to ensure the optimality of the IOI strategy.     

L1 shortest paths among polygonal obstacles in the plane

We present an algorithm for computingL ₁ shortest paths among polygonal obstacles in the plane. Our algorithm employs the continuous Dijkstra technique of propagating a wavefront and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of events. By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space.Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(n^–1/2 log² n) time andO(n^–1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL ₁ Voronoi diagram for source points that lie among a collection of polygonal obstacles.Partially supported by a grant from Hughes Research Laboratories, Malibu, California and by NSF Grant ECSE-8857642. Much of this work was done while the author was a Ph.D. student at Stanford University, under the support of a Howard Hughes Doctoral Fellowship, and an employee of Hughes Research Laboratories.     

存在环境约束的机器人自适应迭代学习控制

针对存在不确定性和外界干扰的受限机器人系统提出一种自适应迭代学习控制律.不确定性参数被估计在时间域内,同时重复性外界干扰在迭代域内得到补偿.通过引入饱和学习函数,保证了闭环系统所有信号有界.借助Lyapunov复合能量函数法,证明了系统渐进收敛到期望轨迹的同时,能够保证力跟踪误差有界可调.     

An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon

Abstract. In this paper we study the collision-free path planning problem for a point robot, whose path is of bounded curvature (i.e., constrained to have curvature at most 1), moving in the plane inside an n -sided simple polygon P . Given two points s and t inside P and two directions of travel, one at s and one at t , the problem is to compute a convex and simple path of bounded curvature inside P from s to t consisting of straight-line segments and circular arcs such that (i) the radius of each circular arc is at least 1, (ii) each segment on the path is the tangent between the two consecutive circular arcs on the path, (iii) the given initial direction at s is tangent to the path at s and (iv) the given final direction at t is tangent to the path at t . We propose an O(n ⁴ ) time algorithm for this problem. Using the notion of complete visibility, P is pruned to another polygon P' such that any convex and simple path from s to t inside P also remains inside P' . Then our algorithm constructs the locus of center of a circle of unit radius translating along the boundary of P' and, using this locus, the algorithm constructs a convex and simple path of bounded curvature. Our algorithm is based on the relationship between the Euclidean shortest path, link paths and paths of bounded curvature, and uses several properties derived here on convex and simple paths of bounded curvature. We also show that the path computed by our algorithm can be transformed in O(n) time to a minimal convex and simple path of bounded curvature. Using this transformation and two necessary conditions proposed here for the shortest convex and simple path of bounded curvature, a minimal bounded curvature path is located in O(n ⁴ ) time whose length, except in special situations involving arcs of length greater than π , is at most twice the length of a shortest convex and simple path of bounded curvature.     

多机器人系统中的动态避碰规划

研究冲突区域中多机器人间的协调和避碰问题。采用集中-分布相结合的规划方法,根据系统的拓扑结构为每个机器人规划路径,在冲突区域内使用优先级策略对机器人的运动特征进行分布式规划。通过上下层智能的融合,提高整个系统的智能。     

最短路径方法在宗地估价中的应用

最短路径分析是地理信息系统（GIS）网络分析中的一项重要功能,尝试将其应用到宗地估价中,以实现基准地价修正法中定量修正因素——距离的计算机自动提取。对于空间数据拓扑关系的建立、数据的预处理以及最短路径的求取等具体的实现进行了详细介绍。     

Manipulation of polygonal objects with two wheeled-tip fingers: Planning in the presence of contact position error

This paper addresses the planning problem of object manipulation using wheeled-tip robots considering the wheel-object contact positioning error. The term wheeled-tip refers to a new mechanism that incorporates active wheels at robot’s fingertips and allows the grasp contact-point to move along the object’s surface. The benefits of unlimited rolling contact is achieved at the cost of contact positioning error that may cause the manipulation to fail. We propose a probabilistic based algorithm for robot motion planning that in addition to being collision free, guarantees the stability of the grasp throughout the planned path. To do so, first we introduce an algorithm that ensures the kinematical stability of the grasp during manipulation by respecting the force closure constraint. Further we extend the algorithm to address the practical uncertainties involved in the position of wheel-object contact points. The proposed algorithms can be employed for manipulators with limited rolling contacts, as well. The algorithms have been tested and the results prove that the planned path can be trusted in uncertain situations.     

Initial condition of costate in linear optimal control using convex analysis

The Pontryagin Maximum Principle is one of the most important results in optimal control, and provides necessary conditions for optimality in the form of a mixed initial/terminal boundary condition on a pair of differential equations for the system state and its conjugate costate. Unfortunately, this mixed boundary value problem is usually difficult to solve, since the Pontryagin Maximum Principle does not give any information on the initial value of the costate. In this paper, we explore an optimal control problem with linear and convex structure and derive the associated dual optimization problem using convex duality, which is often much easier to solve than the original optimal control problem. We present that the solution to the dual optimization problem supplements the necessary conditions of the Pontryagin Maximum Principle, and elaborate the procedure of constructing the optimal control and its corresponding state trajectory in terms of the solution to the dual problem.