AGVS避碰问题相关算法研究

摘要

AGVS(自动导引小车系统)近几年来日益成为现代化生产制造系统中柔性化、集成化的重要保证，但如何能使AGVS在现代化生产制造系统中高效的运行，特别是如何使AGVS在日益复杂的生产制造系统中无碰撞的运行，成为了这几年研究的热点和重点。 为了解决AGVS(自动导引小车系统)中的避碰问题，近几年来国内外的学者作了很多的工作，其中1991年C.W.Kim提出了CFSTP算法，为这一领域的工作做了奠基性的工作，然后不断有人对这一算法做改进工作，本文正是在国内外学者工作的基础上，针对CFSTP算法存在的一些问题，提出了一种新的改进算法，仿真结果显示改进算法能够取得比较满意的效果。 同时需要指出AGVS碰撞的存在，是一种的特殊的死锁现象，针对国内外学者普遍关心的AGVS中的循环死锁问题，目前已经提出的算法存在着效率低和搜索死锁类型不全的问题，本文利用Petri网和图论的有关知识，提出了一个改进算法，解决了上述问题。 本文围绕着AGVS中CFSTP算法的改进和循环死锁搜索算法的改进，进行了理论与实际应用的研究，主要内容如下： (1) 对AGV系统在国内外的发展情况作了简单的介绍。 (2) 对国内外的避碰算法进行了介绍，并对研究的现状进行了展望。 (3)本文提出一种GFSTP算法的改进算法，用Dijkstra算法为各AGv规划一条从起点到终点用时最省的路径，然后探测有无碰撞发生，如果发生则根据改进算法进行调整，仿真显示该方法能够取得不错的效果。 (4) 针对循环死锁搜索类型不全的问题，本文提出了一个改进算法。

目录

文摘

英文文摘

论文说明：主要符号表

学位论文独创性声明及知识产权权属声明

第一章绪论

1.1 AGV的定义

1.2AGV的特点

1.3AGV的分类

1.3.1按导航方式分类

1.3.2按执行功能分类

1.4AGV应用的主要领域

1.5AGV的国内外的发展情况

1.5.1国外的发展情况

1.5.2国内的发展情况

1.6AGV的发展方向

1.7论文章节安排和所做主要工作

1.7.1论文章节安排

1.7.2本文所做主要工作

第二章避碰问题研究综述

2.1避碰问题的分类与描述

2.1.1避碰问题的分类

2.1.2多AGV之间的避碰规划的数学模型

2.2多AGV避碰算法

2.2.1基于图论的方法

2.2.2着色Petri网方法

2.2.3博奕论与最优控制理论结合的方法

2.2.4 CFSTP算法

2.2.5道路图(road map)方法

2.2.6区域控制方法

2.2.7拟阵方法

2.3避碰问题国内外研究的动态

第三章CFSTP算法改进研究

3.1CFSTP方法介绍

3.1.1时间窗的原始定义

3.1.2自由时间窗的定义

3.1.3 CFSTP算法中几个符号的说明

3.1.4 CFSTP算法的伪码描述

3.1.5 CFSTP方法存在的一些局限

3.2目标函数的设计

3.3Dijkstra算法介绍

3.4避碰规划问题的数学模型

3.4.1符号与定义的说明

3.4.2该问题的数学公式的表述

3.4.3约束条件的解释：

3.5改进方法的思路

3.5.1问题假设与碰撞判据

3.5.2算法设计

3.5.3改进方法的适用范围

3.5.4正确性的证明

3.5.5最优性的证明

3.6数值实例

3.7比较与分析

3.8改进算法的复杂性分析

第四章AGVS中循环死锁搜索算法的改进研究

4.1 AGVS循环死锁搜索问题的定义和数学模型

4.1.1面向资源的着色petri网(CORPN)定义死锁

4.1.2 T-R图定义死锁

4.1.3 Petri网与T-R图之间的关系

4.2引起死锁现象的原因

4.3循环死锁的分类

4.4有关定义的说明

4.5循环死锁搜索算法简介

4.5.1主要循环死锁搜索算法简单介绍

4.5.2国内外的研究现状

4.6循环死锁搜索算法存在的局限

4.7循环死锁搜索改进算法的讨论

4.7.1循环死锁是否存在的判断算法

4.7.2搜索T-R图中所有循环死锁的算法

4.7.3循环死锁搜索算法

4.7.4实例分析

4.7.5循环死锁搜索改进算法正确性的证明

4.8比较与分析

第五章总结与展望

参考文献

致谢

附录1 Dijkstra算法介绍

附录2 攻读学位期间发表的论文