一种基于Dijkstra算法的机器人避障问题路径规划

移动机器人的避障问题是移动机器人控制领域的研究热点.针对给定的移动机器人避障问题,探讨了最短路径及最短时间路径的路径规划问题.对于最短路径问题,建立了简化的路径网格模型,将其抽象为由节点及边构成的两维图,再使用经典的Dijkstra算法获得可行的最短路径.对于最短时间路径问题,通过分析移动机器人弯道运行的速度曲线,基于几何方法得出了移动时间与过渡圆弧圆心之间严格的数学关系,此后借助MATLAB优化函数获得最佳的移动路径.算法可为类似机器人避障问题的解决提供借鉴.     

基于五次Hermite插值的机械臂最短路径规划研究

为了保证机械臂高效率和平稳的运行,机械臂运动轨迹曲线一般需要具有C~2连续性,且运动路径具有最优性.采用五次Hermite插值函数方法,构造机械臂的运动轨迹.求解最优化问题得到连接点处二阶导数信息,构造满足上述条件的曲线轨迹,最后给出了两个实例来验证该方法的有效性.     

Resource Constrained Shortest Path Problems in Path Planning for Fleet Management

In the management and control of a vehicle fleet on a road network, the problem arises of finding the best route in relation to the mission of the fleet and to the typology of freight or users. Sometimes the route has to be adapted not only to current traffic conditions, but also to the physical, geometric and functional attributes of the roads, related to their urban location and environmental characteristics. This problem is approached here through an extension of the classic Shortest Path problem, named Resource Constrained Shortest Path problem (RCSP), where the resources are related to the road link attributes, assumed as relevant to the specific planning problem. A classification scheme of these attributes is first proposed and RCSP is described and reviewed. Next, a General Resource Constrained Shortest Path problem (GRCSP) is defined, which can be found in all cases where it is necessary to plan, statically or dynamically, the path of a vehicle and to respect a set of constraints expressed in terms of parameters and indices associated with the roads on the network. For this general problem a model has been formulated and a Branch and Cut solution approach is proposed. Computational results obtained on test and real networks during the experimentation of a fleet with low emission vehicles are also given. This revised version was published online in August 2006 with corrections to the Cover Date.     

基于改进蚁群算法的侦察无人机航路规划与实现

文章针对侦察无人机航路规划这一问题,分析了影响航路规划的因素,构建了航路规划的模型.结合侦察无人机航路规划的特点与模型,论证了基于蚁群算法求解的理由与优点,并对蚁群算法的初始信息素强度与启发因子进行了改进.最后以岛屿进攻战役这一特定作战任务为例,利用MATLAB实现了侦察多目标时的航路规划问题.     

机器人路径规划算法及其应用

本文研究环境已知条件下的移动机器人路径规划问题,提出了一种基于人工神经网络的路径规划算法,所提算法可以规划出折线型的最短路径,并且计算简单,收敛速度快。将所提算法应用于机器人“Khepera“,通过模拟实验,表明所提算法有效。     

Optimal Two-Agent Coordination for Graph Traversal: When Is Formation Travel Beneficial?

The objective of this paper is to pose and solve a simple class of coordinated motion problems that capture the following question; When is formation travel optimal? This class of problems is complementary to two related classes of problems that have received significant attention: close formation travel and the generation of flocking behavior. We pose and solve this problem for the case of two agents traversing a finite, connected graph. Two examples are provided, illustrating the application of the results.     

基于组织与行业可见度的企业慈善捐助水平研究

以汶川地震和玉树地震为背景,通过多元回归模型,探讨了在灾害事件背景下,组织可见度、行业可见度、企业规模和利润水平对企业慈善捐助水平的影响.结果表明,企业规模与企业慈善捐助数量并没有呈现出三阶段特征(正-负-正),而是明显正相关关系;而当控制了企业规模和公司利润水平后,虽然组织可见度对企业慈善捐助水平有明显的积极影响,但经济因素(企业规模)仍然是影响企业慈善捐助水平的最主要因素;此外,企业利润水平对企业慈善捐助水平有着明显的积极影响;最后,行业可见度对企业慈善捐助水平并不存在显著影响.     

基于核和灰度的灰色网络计划技术

针对工程项目工作持续时间具有灰色不确定性特征的实际问题,结合灰色系统理论,提出了基于核和灰度的灰色网络计划技术.考虑业主方进度偏好,构造灰工作三角形白化权函数,然后以三角形重心横坐标为灰工作的核,以要求工期为论域计算灰工作的灰度,并以核和灰度表示的简化形式构建了灰工作网络计划.给出了灰工作网络计划时间参数计算方法,并探讨了灰关键路径的判定方法.案例分析验证了方法的科学性和有效性.     

基于小波分析的空间机械臂运动规划的最优控制

讨论了空间机械臂系统非完整运动规划的最优控制问题.利用小波分析方法,将离散正交小波函数引入最优控制,由小波级数展开式逼近替代传统的Fourier基函数,提出基于小波分析的最优控制数值算法.仿真结果表明,该方法对求解空间机械臂非完整运动规划问题是有效的.     

An Affine Scaling Interior Trust Region Method via Optimal Path for Solving Monotone Variational Inequality Problem with Linear Constraints

Based on a differentiable merit function proposed by Taji et al. in ＂Math. Prog. Stud., 58, 1993, 369-383＂, the authors propose an affine scaling interior trust region strategy via optimal path to modify Newton method for the strictly monotone variational inequality problem subject to linear equality and inequality constraints. By using the eigensystem decomposition and affine scaling mapping, the authors form an affine scaling optimal curvilinear path very easily in order to approximately solve the trust region subproblem. Theoretical analysis is given which shows that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions.     

Solving some optimal path planning problems using an approach based on measure theory

In this paper we solve a collection of optimal path planning problems using a method based on measure theory. First we consider the problem as an optimization problem and then we convert it to an optimal control problem by defining some artificial control functions. Then we perform a metamorphosis in the space of problem. In fact we define an injection between the set of admissible pairs, containing the control vector function and a collision-free path defined on free space and the space of positive Radon measures. By properties of this kind of measures we obtain a linear programming problem that its solution gives rise to constructing approximate optimal trajectory of the original problem. Some numerical examples are proposed.     

灰色网络计划中的关键线路确定方法研究

由于目前区间灰数的表征和运算过程存在着运算结果对灰数的灰度进行不必要的放大,造成信息的严重失真的问题,所以在灰色网络计划中计算出的工作总时差也有不同程度的放大,这时再根据工作总时差为零或最小的方法来确定关键线路则是不准确的.给出了确定灰色网络计划关键线路可以根据关键线路上总工期最长的方法,简单易行,且有效避免了灰数运算对灰数灰度放大的问题.     

紧急疏散中最优抗出错路径选择模型与算法

疏散路径选择是紧急疏散中的重要问题,为了减小疏散人在紧急疏散过程中由于路径选择错误带来的损失,提出一对起讫点间最优抗出错路径选择模型。给出路径出错系数的定义,用以度量疏散人路径选择错误带来的疏散效率损失,并且设计了求解最优抗出错路径的DAE算法,证明该算法的时间复杂度为O（ mn2）。结果表明,选择最优抗出错路径作为疏散路径,能够有效地抵抗由于疏散人路径选择错误带来的损失,对提高突发事件下的疏散效率具有实际意义。     

带有模糊容量限制的网络中的最佳最小费用最大流

本文主要讨论当网络中的弧容量限制和最大流目标要求带有模糊性时的最小费用最大流问题，通过构造带费用的增量网络并设法寻找其中的最佳最小费用路，给出了求解这类模糊网络流问题的算法。     

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

一种改进的公交网络最优路径算法

通过对公交网络模型进行分析,考虑公交线路票价变化,按照出行时间最短同时保证换乘次数较少的原则,对现有解决公交网络最短路问题的算法进行改进.应用了将公交线路抽象为顶点,建立邻接矩阵的方法处理换乘问题.通过实际问题计算验证了算法的有效性.     

搜索路径的优化设计模型

研究对指定区域进行全面搜索用时最少的行进路线.问题一中提出了往复式的搜索方式,结合拐弯处所用的时间,得到最优时间为49.806小时,添加三名队员后,最优时间为46.593小时:对问题二提出了分组进行搜索的方式,当分组队员数分别为22、23、5人时,最优时间为20.45小时.     

模糊计划评审技术(F-PERT)中关键路径的规划解法

研究了模糊计划评审技术中关键路径的求解方法 .首先建立了模糊计划网络图中寻找关键路径的规划模型 ,指出该规划模型在模糊排序规则下可以转化为多目标线性规划问题 ,并给出了该类多目标线性规划问题的求解步骤 .最后的算例表明 ,文中提出的方法是切实可行的 .     

Optimal wire ordering and spacing in low power semiconductor design

A key issue for high integration circuit design in the semiconductor industry are power constraints that stem from the need for heat removal and reliability or battery lifetime limitations. As the power consumption depends heavily on the capacitances between adjacent wires, determining the optimal ordering and spacing of parallel wires is an important issue in the design of low power chips. As it turns out, optimal wire spacing is a convex optimization problem, whereas the optimal wire ordering is combinatorial in nature, containing (a special class of) the Minimum Hamilton Path problem. While the latter is ${\mathcal{NP}}A key issue for high integration circuit design in the semiconductor industry are power constraints that stem from the need for heat removal and reliability or battery lifetime limitations. As the power consumption depends heavily on the capacitances between adjacent wires, determining the optimal ordering and spacing of parallel wires is an important issue in the design of low power chips. As it turns out, optimal wire spacing is a convex optimization problem, whereas the optimal wire ordering is combinatorial in nature, containing (a special class of) the Minimum Hamilton Path problem. While the latter is -hard in general, the present paper provides an algorithm that solves the coupled ordering and spacing problem for N parallel wires to optimality. Dedicated to Prof. Martin Gr?tschel on the occasion of his 60th birthday.