A Branching Time Temporal Framework for Quantitative Reasoning

Temporal logics such as Computation Tree Logic (CTL) and Linear Temporal Logic (LTL) have become popular for specifying temporal properties over a wide variety of planning and verification problems. In this paper we work towards building a generalized framework for automated reasoning based on temporal logics. We present a powerful extension of CTL with first-order quantification over the set of reachable states for reasoning about extremal properties of weighted labeled transition systems in general. The proposed logic, which we call Weighted Quantified Computation Tree Logic (WQCTL), captures the essential elements common to the domain of planning and verification problems and can thereby be used as an effective specification language in both domains. We show that in spite of the rich, expressive power of the logic, we are able to evaluate WQCTL formulas in time polynomial in the size of the state space times the length of the formula. Wepresent experimental results on the WQCTL verifier.     

带有时钟变量的线性时序逻辑与实时系统验证

为了描述实时系统的性质和行为,10多年来,各种不同的时序逻辑,如Timed Computation Tree Logic,Metric Interval Temporal Logic和Real-Time Temporal Logic等相继提出来.这些时序逻辑适于表示实时系统的性质和规范,但不适于表示实时系统的实现模型.这样,在基于时序逻辑的实时系统的研究中,系统的性质和实现通常是用两种不同的语言来表示的.定义了一个带有时钟变量的线性时序逻辑(linear temporal logic with clocks,简称LTLC).它是由Manna和Pnueli提出的线性时序逻辑在实时情况下的一个推广.LTLC既能表示实时系统的性质,又能很方便地表示实时系统的实现.它能在统一的语义框架中表示出从高级的需求规范到低级的实现模型之间的不同抽象层次上的系统描述,并且能用逻辑蕴涵来表示不同抽象层次的系统描述之间的语义一致性.LTLC的这个特点将有助于实时系统的性质验证和实时系统的逐步求精.     

TCTL Inevitability Analysis of Dense-Time Systems: From Theory to Engineering

Inevitability properties in branching temporal logics are of the syntax foralldiamondsuit phi, where phi is an arbitrary (timed) CTL (Computation Tree Logic) formula. Such inevitability properties in dense-time logics can be analyzed with the greatest fixpoint calculation. We present algorithms to model-check inevitability properties. We discuss a technique for early decision on greatest fixpoint calculation which has shown promising performance against several benchmarks. We have experimented with various issues which may affect the performance of TCTL inevitability analysis. Specifically, our algorithms come with a parameter for the measurement of time-progress. We report the performance of our implementation with regard to various parameter values and with or without the non-Zeno computation requirement in the evaluation of greatest fixpoints. We have also experimented with safe abstraction techniques for model-checking TCTL inevitability properties. The experiment results help us in deducing rules for setting the parameter for verification performance. Finally, we summarize suggestions for configurations of efficient TCTL inevitability evaluation procedure.     

Abstraction and approximation in fuzzy temporal logics and models

Recently, by defining suitable fuzzy temporal logics, temporal properties of dynamic systems are specified during model checking process, yet a few numbers of fuzzy temporal logics along with capable corresponding models are developed and used in system design phase, moreover in case of having a suitable model, it suffers from the lack of a capable model checking approach. Having to deal with uncertainty in model checking paradigm, this paper introduces a fuzzy Kripke model (FzKripke) and then provides a verification approach using a novel logic called Fuzzy Computation Tree Logic* (FzCTL*). Not only state space explosion is handled using well-known concepts like abstraction and bisimulation, but an approximation method is also devised as a novel technique to deal with this problem. Fuzzy program graph, a generalization of program graph and FzKripke, is also introduced in this paper in consideration of higher level abstraction in model construction. Eventually modeling, and verification of a multi-valued flip-flop is studied in order to demonstrate capabilities of the proposed models.     

Three-valued abstraction for probabilistic systems

This paper proposes a novel abstraction technique for fully probabilistic systems. The models of our study are classical discrete-time and continuous-time Markov chains (DTMCs and CTMCs, for short). A DTMC is a Kripke structure in which each transition is equipped with a discrete probability; in a CTMC, in addition, state residence times are governed by negative exponential distributions. Our abstraction technique fits within the realm of three-valued abstraction methods that have been used successfully for traditional model checking. The key ingredients of our technique are a partitioning of the state space combined with an abstraction of transition probabilities by intervals. It is shown that this provides a conservative abstraction for both negative and affirmative verification results for a three-valued semantics of PCTL (Probabilistic Computation Tree Logic). In the continuous-time setting, the key idea is to apply abstraction on uniform CTMCs which are readily obtained from general CTMCs. In a similar way as for the discrete case, this is shown to yield a conservative abstraction for a three-valued semantics of CSL (Continuous Stochastic Logic). Abstract CTMCs can be verified by computing time-bounded reachability probabilities in continuous-time MDPs.     

动态环境下基于概率模型检测的路径规划方法

提出了一种动态复杂环境下采用概率模型检测技术进行路径规划的新方法。考虑到实际应用中机器人其移动行为总是受到外界因素的影响,将机器人移动行为看作一个不确定事件,提取环境中的影响因素,构建马尔可夫决策过程模型。采用时态逻辑语言描述机器人目标任务,表达复杂多样的需求行为。运用工具PRISM验证属性,得到满足任务需求的全局优化路径。另外,在全局路径的基础上提出了一种动态避障策略,实现避障局部规划的同时尽量保证机器人最大概率完成任务。通过理论和仿真实验结果证明该方法的正确性和有效性。     

Conflict free coordinated path planning for multiple robots using a dynamic path modification sequence

In this paper, a practically viable approach for conflict free, coordinated motion planning of multiple robots is proposed. The presented approach is a two phase decoupled method that can provide the desired coordination among the participating robots in offline mode. In the first phase, the collision free path with respect to stationary obstacles for each robot is obtained by employing an A* algorithm. In the second phase, the coordination among multiple robots is achieved by resolving conflicts based on a path modification approach. The paths of conflicting robots are modified based on their position in a dynamically computed path modification sequence (PMS). To assess the effectiveness of the developed methodology, the coordination among robots is also achieved by different strategies such as fixed priority sequence allotment for motion of each robot, reduction in the velocities of joints of the robot, and introduction of delay in starting of each robot. The performance is assessed in terms of the length of path traversed by each robot, time taken by the robot to realize the task and computational time. The effectiveness of the proposed approach for multi-robot motion planning is demonstrated with two case studies that considered the tasks with three and four robots. The results obtained from realistic simulation of multi-robot environment demonstrate that the proposed approach assures rapid, concurrent and conflict free coordinated path planning for multiple robots.     

Specification of Real-Time Systems in UML

We introduce time semantics into UML class and statechart diagrams. This extends the expressiveness of UML for specification of real-time systems and allows to specify verification properties of real-time systems by means of Timed Computation Tree Logic. We furthermore propose a way to collect stereotypes for specification of real-time systems. The approach is illustrated by a case study.     

Quantitative temporal reasoning

A substantially large class of programs operate in distributed and real-time environments, and an integral part of their correctness specification requires the expression of time-critical properties that relate the occurrence of events of the system. We focus on the formal specification and reasoning about the correctness of such programs. We propose a system of temporal logic, RTCTL (Real-Time Computation Tree Logic), that allows the melding of qualitative temporal assertions together with real-time constraints to permit specification and reasoning at the twin levels of abstraction: qualitative and quantitative. We argue that many practically useful correctness properties of temporal systems, which need to express timing as an essential part of their functionality requirements, can be expressed in RTCTL. We develop a model-checking algorithm for RTCTL whose complexity is linear in the size of the RTCTL specification formula and in the size of the structure. We also present an essentially optimal, exponential time tableau-based decision procedure for the satisfiability of RTCTL formulae. Finally, we consider several variants and extensions of RTCTL for real-time reasoning.The work of E.A. Emerson was supported in part by NSF grant DCR-8511354, ONR URI contract N00014-86-K-0763, and Netherlands NWO grant nf-3/nfb 62-500. The work of A.K.Mok was supported in part by ONR Grant number N00014-89-J-1472 and Texas Advanced Technology Program Grant 003658-250. A summary of these results was presented at the Workshop on Automatic Verification Methods for Finite State Systems, Grenoble, France, June 12–14, 1989.     

平面复杂边缘的双机器人协调跟踪运动规划研究

研究双机器人协调跟踪平面复杂边缘所涉及的问题.在笛卡儿空间内对跟踪任务进行协调分解,并分析双机器人的位置约束关系,采用双曲线函数规划双机器人基于关节空间的运动轨迹,以满足位置、速度以及加速度等平滑运动的约束条件,采用基于曲线极大值的分段跟踪算法扩展平面复杂曲线的一般性.仿真实验和应用均表明了所研究内容的可行性和正确性.     

Quantified Computation Tree Logic

Computation Tree Logic (CTL) is one of the most syntactically elegant and computationally attractive temporal logics for branching time model checking. In this paper, we observe that while CTL can be verified in time polynomial in the size of the state space times the length of the formula, there is a large set of reachability properties which cannot be expressed in CTL, but can still be verified in polynomial time. We present a powerful extension of CTL with first-order quantification over sets of reachable states. The extended logic, QCTL, preserves the syntactic elegance of CTL while enhancing its expressive power significantly. We show that QCTL model checking is PSPACE-complete in general, but has a rich fragment (containing CTL) which can be checked in polynomial time. We show that this fragment is significantly more expressive than CTL while preserving the syntactic beauty of CTL.     

基于运动性能分析的双臂冗余度机器人协调运动研究

为了提高双臂冗余度机器人在其交互工作空间中的协调运动能力,以ABB YuMi为例,提出了一种计算简便并且能够有效反映双臂协调运动灵活性的性能指标。利用D-H法建立了YuMi机器人的运动学模型,分析了双臂可操作度的分布情况,分别研究了两种协调运动方式的运动学约束关系以及相应的运动控制规律,基于灵活性分析构建了双臂协调装配电机转子与轴承以及字母绘制的任务,通过仿真和实验验证了本文双臂可操作度指标的有效性及协调运动规划方法的正确性。     

A Complete and Scalable Strategy for Coordinating Multiple Robots Within Roadmaps

This paper addresses the challenging problem of finding collision-free trajectories for many robots moving toward individual goals within a common environment. Most popular algorithms for multirobot planning manage the complexity of the problem by planning trajectories for robots individually; such decoupled methods are not guaranteed to find a solution if one exists. In contrast, this paper describes a multiphase approach to the planning problem that uses a graph and spanning tree representation to create and maintain obstacle-free paths through the environment for each robot to reach its goal. The resulting algorithm guarantees a solution for a well-defined number of robots in a common environment. The computational cost is shown to be scalable with complexity linear in the number of the robots, and demonstrated by solving the planning problem for 100 robots, simulated in an underground mine environment, in less than 1.5 s with a 1.5 GHz processor. The practicality of the algorithm is demonstrated in a real-world application requiring coordinated motion planning of multiple physical robots.     

QRDChecker:一个QRDC模型检验工具

反应式系统通常是不终止的,其行为定义为系统状态的无限序列的集合.形式化验证时,检验需求一般使用时序逻辑给出.当使用诸如LTL(linear temporal logic)这样的逻辑时,由于这类逻辑的模型同样是无限序列,系统与需求之间的满足性关系可以简单定义为集合的包含关系.但是,当使用时段时序逻辑(interval temporal logic)作为说明逻辑时,由于逻辑模型的有限性,使得上面的满足关系不再适用.称这类有限序列集合表达的性质为有限性性质.对于不同的有限性性质,它们对应的满足性关系是有区别的.针对两类有限性定义了它们各自的满足性关系,并将这两种关系统一为一个更一般的满足性关系.在此基础上,提出模型检验这两类性质的算法,并将其实现为一个针对时段时序逻辑QRDC(quantified RDC (restricted duration calculus))的检验工具QRDChecker.QRDChecker可以检验QRDC公式在连续时间模型和离散时间模型下的有效性.在离散时间条件下,它还可以将QRDC公式转换成模型检验系统Spin能够接受的自动机的形式,从而可以检查反应式系统是否满足用QRDC公式表达的性质.     

Control of nondeterministic discrete-event systems for bisimulation equivalence

Most prior work on supervisory control of discrete event systems is for achieving deterministic specifications, expressed as formal languages. In this paper we study supervisory control for achieving nondeterministic specifications. Such specifications are useful when designing a system at a higher level of abstraction so that lower level details of system and its specification are omitted to obtain higher level models that may be nondeterministic. Nondeterministic specifications are also meaningful when the system to be controlled has a nondeterministic model due to the lack of information (caused for example by partial observation or unmodeled dynamics). Language equivalence is not an adequate notion of behavioral equivalence for nondeterministic systems, and instead we use the finest known notion of equivalence, namely the bisimulation equivalence. Choice of bisimulation equivalence is also supported by the fact that bisimulation equivalence specification is equivalent to a specification in the temporal logic of /spl mu/-calculus that subsumes the complete branching-time logic CTL*. Given nondeterministic models of system and its specification, we study the design of a supervisor (possibly nondeterministic) such that the controlled system is bisimilar to the specification. We obtain a small model theorem showing that a supervisor exists if and only if it exists over a certain finite state space, namely the power set of Cartesian product of system and specification state spaces. Also, the notion of state-controllability is introduced as part of a necessary and sufficient condition for the existence of a supervisor. In the special case of deterministic systems, we provide an existence condition that can be verified polynomially in both system and specification states, when the existence condition holds.     

面向全方位双足步行跟随的路径规划

双足步行机器人的足迹规划方法难以满足快速步行条件下的计算效率要求, 并存在步幅变化时运动失稳的风险, 2D环境下点机器人栅格规划则难于生成针对双足步行的高效路径.本文提出针对各向异性特征全方位步行机器人的一种路径规划策略, 将状态网格图方法拓展到全方位移动机器人领域, 基于三项基本假设及基元类型划分给出了系统的运动基元枚举及选择方法, 借助实时修正的增量式AD*搜索算法实现仿人机器人在动态环境下的快速路径规划, 通过合理选择启发函数及状态转移代价, 生成了平滑高效的路径, 为后续足迹生成的动力学优化提供了基础.计算机仿真证实了方法对各类环境的适应性, Robocup避障竞速挑战赛的成功表现证明了方法对于机器人样机部署的可行性及其提高步行效率的潜力.     

Safe and efficient motion planning of multiple mobile robots based on artificial potential for human behavior and robot congestion

In order for robots to exist together with humans, safety for the humans has to be strictly ensured. On the other hand, safety might decrease working efficiency of robots. Namely, this is a trade-off problem between human safety and robot efficiency in a field of human–robot interaction. For this problem, we propose a novel motion planning technique of multiple mobile robots. Two artificial potentials are presented for generating repulsive force. The first potential is provided for humans. The von Mises distribution is used to consider the behavioral property of humans. The second potential is provided for the robots. The Kernel density estimation is used to consider the global robot congestion. Through simulation experiments, the effectiveness of the behavior and congestion potentials of the motion planning technique for human safety and robot efficiency is discussed. Moreover, a sensing system for humans in a real environment is developed. From experimental results, the significance of the behavior potential based on the actual humans is discussed. For the coexistence of humans and robots, it is important to evaluate a mutual influence between them. For this purpose, a virtual space is built using projection mapping. Finally, the effectiveness of the motion planning technique for the human–robot interaction is discussed from the point of view of not only robots but also humans.     

被动冗余度空间机器人运动学综合

分析了“被动冗余度”空间机器人主,被动关节之间的运动学耦合,得到了可用于运动 学规划的耦合指标;分析了“被动冗余度”空间机器人的运动学奇异问题,以及与对应全主 动关节冗余度空间机器人的运动学奇异的区别,得到的新的可操作性指标同样可用于机器人 的运动规划;推导出了“被动冗余度”空间机器人的最佳最小二乘运动学优化方程,通过“ 准自运动”实现被动冗余度空间机器人优化控制;通过对平面3DOF空间站机器人的仿真证实 了分析得到的结论．     

Multi-robot spot-welding cells for car-body assembly: Design and motion planning

Multi-robot cells for spot welding use coordinated robots to assemble metal panels via spot welding by coordinated robots, for instance in the construction of car doors. The design of multi-robot cells for spot welding required both cell design and off-line motion planning. Cell design involves resource selection (such as robots and welding guns) and resource configuration, while considering cell productivity, costs, flexibility and reconfigurability. Motion planning involves allocating welding points to each resource and calculating collision-free motion plan for each robot. Currently, cell design and motion planning are sequential and manual activities, managed by different and separate industrial functional units. This results in several cycles before the design converges to a feasible final solution. The proposed approach introduces a unified methodology, aiming at optimizing the holistic cell design and motion planning, that reduces design time and errors. The feasibility of the proposed approach has been demonstrated in several ad-hoc basic replicable cases and in one industrial case. The outcome of this research improves state of the art, reducing design and motion planning time over current technology. Moreover, the method has been integrated into a computerized approach which has the potential to accelerate the whole cell design and motion planning processes and to reduce human efforts.     

一种输电线路巡检机器人越障规划方法

针对输电线路巡检机器人的局部自主与远程控制方式,提出了一种基于有限状态机的越障规划方法.将巡检机器人的越障运动过程分解成若干离散化的关键状态,建立了运动规划的有限状态机模型.采用一种基于模糊方法的产生式系统用于推理越障模式,并产生运动序列.仿真与现场实验验证了越障规划方法的正确性和有效性,该方法可应用于输电线路巡检机器人运动控制.