一种基于可视图的机器人避障路径规划

该文首先提出用Minkowski和的工具将多边形机器人的路径规划问题转化为点机器人的情况,然后基于移动机器人的安全考虑,提出了一种改进的可视图法。该方法用尽可能远离障碍物的路径表示弧,先确定可能的路径点作为节点,然后考虑可能路径,建立结点间的弧,并用Dijkstra算法求出图中的最短路径。最后通过仿真研究表明,用文章提出的方法规划的路径可以达到或接近最优路径。     

图论在网络的可靠性分析中应用——对基于1—critical—path subset网络的性能分析

本文对一种网络流模型的可靠性进行了分析，在这个模型中，我们考虑一对源节点和汇节点的图，它的弧是随机失效的，当网络最大流大于正常工作流，我们就说系统是正常工作的，考虑正常工作流的一种特殊情况，这里，所有的弧都具有相同的容量，在这种特殊的情况中，潜在的系统是1－critical的，也就是说，所有的弧的最小截大小为2，此时，问题转化为有向图中，求所有的失效弧都在同一条路径上的概率，而这个问题可以用多项式算法来解决。     

路径覆盖构造方法

确定覆盖路径的测试数据范围是评估路径测试的重要课题之一。提出利用非限制弧集确定覆盖ddgraph图所有路径的子集，然后利用βtracks简化非限制弧，并给出了具体的应用实例。     

分支点邻域内的奇异路径跟踪

在非冗余机械臂运动学的分支奇异点邻域内，由于出现逆运动学解的分支 现象，用基于零空间的拟弧长法求解路径跟踪问题会遇到困难．为此，本文通过计算分支点 的局部模型，提出从分支点开始向两侧延拓的解曲线计算方法，有效地完成了路径跟踪求解 ，在关节空间获得光滑的运动轨迹．     

基于DDGRAPH图的路径覆盖研究

软件测试分为静态分析、路径选择、测试数据生成和动态分析四个阶段,而路径选择的自动生成是软件测试的关键技术之一。路径覆盖是软件测试中一种十分重要的方法,它使程序的每个分支至少执行一次。文中通过对DDGRAPH图的分析,提出了DDGRAPH图中弧的支配树和蕴含树的表示方法,然后给出由支配树和蕴含树确定非限制弧的方法,通过近似最少谓词覆盖策略以确定覆盖所有非限制弧的路径测试子集。     

DiffServ的MPLS流量工程的实现

提出用现有的技术实现考虑差分服务(DiffServ)的MPLS流量工程的方法，其核心思想是：不是在发起流量的源节点计算出各种可供选择的路径时，而是在为该流量选择合适的路径的时候才考虑DiffServ的约束因案。该方法的优点是算法简单、扩展性强和资源占用少。     

基于DDGRAPH图的路径覆盖研究

软件测试分为静态分析、路径选择、测试数据生成和动态分析四个阶段,而路径选择的自动生成是软件测试的关键技术之一.路径覆盖是软件测试中一种十分重要的方法,它使程序的每个分支至少执行一次.文中通过对DDGRAPH图的分析,提出了DDGRAPH图中弧的支配树和蕴含树的表示方法,然后给出由支配树和蕴含树确定非限制弧的方法,通过近似最少谓词覆盖策略以确定覆盖所有非限制弧的路径测试子集.     

图论在网络的可靠性分析中的应用——对基于 1-critical-Path subset网络的性能分析

本文对一种网络流模型的可靠性进行分析 .在这个模型中 ,我们考虑一对源节点和汇节点的图 ,它的弧是随机失效的 .当网络最大流大于正常工作流 ,我们就说系统是正常工作的 .考虑正常工作流的一种特殊情况 ,这里 ,所有的弧都具有相同的容量 .在这种特殊的情况中 ,潜在的系统是 1- critical的 ,也就是说 ,所有的弧的最小截大小为 2 .此时 ,问题转化为在有向图中 ,求所有的失效弧都在同一条路径上的概率 ,而这个问题可以用多项式算法来解决     

基于路径覆盖的高效编程测试方法研究

目前白盒测试标准,以覆盖程度为依据有6种。其中覆盖程度最高的是路径覆盖,但是传统的用例构造法没有给出达到路径覆盖的方法。本文提出一种能够达到路径覆盖的测试用例编写方法。它用树的形式把程序可能执行的路径解析出来,以达到路径覆盖的目的。此方法在单元测试用例编写中,简单、高效地覆盖程序中各种可能的路径。     

多车场CARP问题的改进遗传算法求解

带有容量限制的弧路径规划问题来源于城市垃圾回收、街道清扫、邮件投递、校车路线安排和洒水车路线安排等实际问题,多车场CARP问题是具有多个车场的CARP问题。提出了一种先划分区域后进行路径规划的方法来求解多车场CARP问题。该方法先将各服务弧按照离车场距离的远近归并到距离最近的车场,从而转化为单车场CARP问题,然后用改进的遗传算法进行求解;在求解过程中,用模拟退火算法对部分服务弧进行局部调整,使服务弧在一定的范围内在不同的车场之间进行调换,从而避免局部收敛,达到全局优化的效果。以洒水车路线安排为实例,实验结果表明,该算法能有效求解一定规模的多车场CARP问题,为实际应用奠定了基础。     

Conversion of the Steiner Problem on the Euclidean Plane to the Steiner Problem on Graph

If in the Steiner problem on graph the number of terminal nodes is much smaller than that of all graph nodes (say 50 against 1000), then one can see in its solution (the minimum tree) a system of paths on the graph connecting the terminal vertices, rather than a collection of separate edges (or arcs). This path system is similar to the system of segments making up the Steiner tree on the Euclidean plane: the local degree of the terminal nodes usually is 1, and the local degree of some nodes making up the paths is 3 or more. These nodes are the counterparts of the Steiner points in the problem on plane. Structural similarity of the trees in the Steiner problems on the Euclidean plane and on graph enables one to construct the algorithm to solve the Steiner problem on graph along the same lines as in the Steiner problem on the Euclidean plane. On the other hand, the solution of a problem on graph may be regarded as that on the Euclidean plane, provided that the graph satisfies certain requirements.     

Synthesis of Decision-Free Concurrent Systems for Prescribed Resources and Performance

This paper presents a method for synthesizing or growing live and safe marked graph models of decision-free concurrent comutations. The approach is modular in the sense that subsystems r represented by arcs (and nodes) are added one by one without the need of redesigning the entire system. The foliowing properties of marked graph models can be prescribed in the synthesis: liveness (absence of deadlocks), safeness (absence of overflows), the number of reachability classes, the maximum resource (temporary storage) requirement, computation rate (performance), as well as the numbers of arcs and states.     

过必经结点集的选择性排序算法

目前研究经过必经结点集的最短路径算法多数是针对不允许存在回路的情况,少数针对存在回路的传统算法时间复杂度相对偏高。对此通过探索最优路径形成的规律,将含有大量结点的图转化为含有少量结点的图,用选择性排序法尽量少地生成路径序列分支,对这些分支进行筛选从而得到最短路径。实验结果表明,在面对数目较多的必经结点时,该算法性能将优于传统算法。     

Algorithms for the Weight Constrained Shortest Path Problem

Given a directed graph whose arcs have an associated cost, and associated weight, the weight constrained shortest path problem (WCSPP) consists of finding a least-cost path between two specified nodes, such that the total weight along the path is less than a specified value. We will consider the case of the WCSPP defined on a graph without cycles. Even in this case, the problem is NP-hard, unless all weights are equal or all costs are equal, however pseudopolynomial time algorithms are known. The WCSPP applies to a number of real-world problems. Traditionally, dynamic programming approaches were most commonly used, but in recent times other methods have been developed, including exact approaches based on Lagrangean relaxation, and fully polynomial approximation schemes. We will review the area and present a new exact algorithm, based on scaling and rounding of weights.     

Automatic generation of path covers based on the control flowanalysis of computer programs

Branch testing a program involves generating a set of paths that will cover every arc in the program flowgraph, called a path cover, and finding a set of program inputs that will execute every path in the path cover. This paper presents a generalized algorithm that finds a path cover for a given program flowgraph. The analysis is conducted on a reduced flowgraph, called a ddgraph, and uses graph theoretic principles differently than previous approaches. In particular, the relations of dominance and implication which form two trees of the arcs of the ddgraph are exploited. These relations make it possible to identify a subset of ddgraph arcs, called unconstrained arcs, having the property that a set of paths exercising all the unconstrained arcs also cover all the arcs in the ddgraph. In fact, the algorithm has been designed to cover all the unconstrained arcs of a given ddgraph: the paths are derived one at a time, each path covering at least one as yet uncovered unconstrained arc. The greatest merits of the algorithm are its simplicity and its flexibility. It consists in just visiting recursively in combination the dominator and the implied trees, and is flexible in the sense that it can derive a path cover to satisfy different requirements, according to the strategy adopted for the selection of the unconstrained arc to be covered at each recursive iteration. This feature of the algorithm can be employed to address the problem of infeasible paths, by adopting the most suitable selection strategy for the problem at hand. Embedding of the algorithm into a software analysis and testing tool is recommended     

An efficient network flow code for finding all minimum cost s–t cutsets

Cutset algorithms have been well documented in the operations research literature. A directed graph is used to model the network, where each node and arc has an associated cost to cut or remove it from the graph. The problem considered in this paper is to determine all minimum cost sets of nodes and/or arcs to cut so that no directed paths exist from a specified source node s to a specified sink node t. By solving the dual maximum flow problem, it is possible to construct a binary relation associated with an optimal maximum flow such that all minimum cost s–t cutsets are identified through the set of closures for this relation. The key to our implementation is the use of graph theoretic techniques to rapidly enumerate this set of closures. Computational results are presented to suggest the efficiency of our approach.Scope and purposeThis paper describes the technical details of a network flow algorithm used to find all minimum cost s–t cutsets in any network topology. The motivation for this work was to provide additional automated analysis capability to a military network targeting system. Specifically, the problem is to identify a minimum cost set of nodes and/or arcs that when removed from the network, will disconnect a selected pair of origin–destination nodes. Algorithms for solving this problem are well understood, with an active research thrust in both the operations research and computer science academic communities in developing more efficient algorithms for larger networks. The main contribution of this paper is in extending these algorithms to quickly find all minimum cost cutset solutions. The implementation described in this paper outperformed conventional methods by several orders of magnitude on networks having thousands of nodes and arcs, with empirical solution times that grew linearly with the network size. The results translate to a real-time cutset analysis capability to support military targeting applications.     

A travelling salesman problem with allocation, time window and precedence constraints — an application to ship scheduling

A Travelling Salesman Problem with Allocation, Time Window and Precedence Constraints (TSP-ATWPC) is considered. The TSP-ATWPC occurs as a subproblem of optimally sequencing a given set of port visits in a real bulk ship scheduling problem, which is a combined multi-ship pickup and delivery problem with time windows and multi-allocation problem. Each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways, thus allowing multiple products to be carried simultaneously by the same ship. The allocation constraints of the TSP-ATWPC ensure that the partition of the ship's flexible cargo hold and the allocation of cargoes to the smaller holds are feasible throughout the visiting sequence. The TSP-ATWPC is solved as a shortest path problem on a graph whose nodes are the states representing the set of nodes in the path, the last visited node and the accumulated cargo allocation. The arcs of the graph represent transitions from one state to another. The algorithm is a forward dynamic programming algorithm. A number of domination and elimination tests are introduced to reduce the state space. The computational results show that the proposed algorithm for the TSP-ATWPC works, and optimal solutions are obtained to the real ship scheduling problem.     

Sketching Clothoid Splines Using Shortest Paths

Clothoid splines are gaining popularity as a curve representation due to their intrinsically pleasing curvature, which varies piecewise linearly over arc length. However, constructing them from hand‐drawn strokes remains difficult. Building on recent results, we describe a novel algorithm for approximating a sketched stroke with a fair (i.e., visually pleasing) clothoid spline. Fairness depends on proper segmentation of the stroke into curve primitives — lines, arcs, and clothoids. Our main idea is to cast the segmentation as a shortest path problem on a carefully constructed weighted graph. The nodes in our graph correspond to a vastly overcomplete set of curve primitives that are fit to every subsegment of the sketch, and edges correspond to transitions of a specified degree of continuity between curve primitives. The shortest path in the graph corresponds to a desirable segmentation of the input curve. Once the segmentation is found, the primitives are fit to the curve using non‐linear constrained optimization. We demonstrate that the curves produced by our method have good curvature profiles, while staying close to the user sketch.