【作者】 张飞；

【导师】 席裕庚； 陈卫东；

【作者基本信息】 上海交通大学 ， 控制科学与工程， 2008， 博士

【摘要】 覆盖问题是目前移动机器人与控制学科研究的前沿课题之一,它反映了机器人移动、感知和协作之间的关系。覆盖问题的本质是机器人或机器人团队利用其移动性将其感知范围逐步覆盖整个环境。在覆盖过程中,每个机器人个体只利用其所能得到的信息来决策其运动,在多个或群体机器人问题中,则可进一步通过有限的通信获取其邻居的信息协助其自身决策,并在整体上实现覆盖任务。研究覆盖的目的是,发现机器人模型和任务本质之间的关系,发现机器人个体通过协作产生整体行为的规律,并应用这些规律设计移动机器人系统和解决实际应用中的问题。本文对单个、多个和群体移动机器人的覆盖问题研究了其建模、控制设计与分析,主要包括以下三个方面:1、针对单个机器人的目标探测和动态覆盖任务,在理论和算法层次利用其约束运动模型和可达区进行问题描述和求解。首先建立了移动机器人约束运动模型和传感器模型用于描述机器人的移动和感知,给出了可达区定义,即机器人在有限步内可能到达的区域,在此基础上证明了在k步不同运动模式下多达2k个可达区的计算可以降为k+1个可达区的计算,并提出了k步可达区由k+1个扇形组成的计算算法。基于约束运动模型和k步可达区,给出了目标探测和动态覆盖的问题描述和求解。针对目标探测问题,定义了可探测区,即机器人在有限步内可能探测到的区域,并提出了探测目标点和最优路径规划算法。对于动态覆盖问题,采用k步已探测区表示机器人通过运动已经探测到的区域,提出了动态覆盖策略和递归算法,并通过仿真结果验证了算法覆盖多边形环境的有效性。2、针对多个机器人如何充分利用通信信息完成覆盖任务的问题,在算法和应用层次提出一种改进市场法实现多机器人覆盖的任务分配。针对市场法只根据本地地图计算代价的局限性,使用标的信息,采用数据融合中的Bayes统计方法更新本地地图,这种改进市场法在连通条件下用以计算原先无法计算的目标点代价,并且没有增加额外的通信量。地图创建采用带有占有概率的栅格地图,同时利用概率论处理不确定性信息,在使用标的信息更新地图时,同样采用概率方法,从而达到整体方法的一致性。我们还提出用目标点切换率这一新指标来衡量机器人间的协作程度。仿真实验以及实机实验结果验证了本算法优于原先的市场法。3、针对群体机器人编队和覆盖任务中机器人缺失和加入情况,在理论和算法层次提出了移动机器人网络接力式切换拓扑控制方法,从整体和个体关系的新角度研究覆盖问题,形成大规模机器人群体建模和控制的理论框架。我们首先建立了结合基于图论的网络拓扑和基于交互动力模型的个体运动模型的移动机器人网络模型。对应地,控制设计也分为上述两个层次:在拓扑层次,通过分析增加和缺失机器人个体对于网络拓扑影响,提出具有自愈性和可扩展性的接力式拓扑控制;在个体层次,将拓扑控制转化为基于局部交互的具有分布式特征的个体控制算法。此外,还提出了一套评价控制算法的指标体系,包括:连通性、收敛性、自愈性、可扩展性、鲁棒性和稳定性,表明了在相同恢复结果下所提出算法的自愈性比已有算法高,关于通信连接缺失的鲁棒性也较高,在切换拓扑的过程中可以保证网络是连通的,并且该算法是收敛的和可扩展的,还给出了具有切换拓扑网络同步稳定性判据。最后分别针对编队和覆盖任务,通过仿真验证了接力式切换拓扑控制算法的有效性,和其它方法比较具有较高的自愈性、可扩展性和鲁棒性。更多还原

【Abstract】 Coverage problem is one of the most challenging research topics in the mobile robotics and control theory, and represents the relationship among mobility, perceptivity and cooperation of robots. Coverage problem is defined as follows: to find a path or paths of the robot or robot groups such that its or their detected region could cover the whole environment with its or their motion. During the process of covering environments, each robot individual can only use the information which could be obtained to decide its motion. For multi-robot or swarm robot, each robot can furthermore obtain the information of its neighbors with finite communication to help its decision, and the whole system shows a collective behavior. The objective of this thesis is to discover the natural relationship between robot models and coverage tasks, to find the natural laws that networked individuals with local interactions can perform different collective behaviors, and to apply these laws to design mobile robot systems and solve problems in practical applications.This thesis provides an in-depth understanding on modeling as well as control method of coverage tasks for single, multi and swarm mobile robot systems, which are fundamental yet challenging issues in this research field. The main contributions in this thesis are divided into the following three aspects:1) For tasks of target detecting and dynamic coverage of single robot, we use mobile robot constrained motion model and reachable region to formulate and solve these problems in a theoretical and algorithmic level. This thesis establishes constrained motion model and sensor model of a mobile robot to represent mobility and perceptivity, respectively, and defines the k step reachable region to describe the states that the robot may reach. We show that the calculation of the k step reachable region can be reduced from that of 2k reachable regions with the fixed motion styles to k + 1 such regions, and provide an algorithm for its calculation. Based on the constrained motion model and the k step reachable region, the problems associated with target detecting and dynamic coverage are formulated and solved. For target detecting, the k step detectable region is used to describe the area that the robot may detect, and an algorithm for detecting a target and planning the optimal path is proposed. For dynamic coverage, the k step detected region is used to represent the area that the robot has detected during its motion, and the dynamic coverage strategy and algorithm are proposed. Simulation results demonstrate the efficiency of the coverage algorithm in both convex and concave environments.2) For the problem of efficiently using finite communication information of multi-robot coverage, we propose an improved market method for task allocation of multi-robot cooperative coverage in an algorithmic and practical level. For the limitation that market-based method only considers costs in the local map of each robot, we update the local maps through fusion of both the local sensor data and the bid information, and thus the extended parts in maps enable robots to calculate costs of other robots’targets. No extra communication is needed. Probability theory is used for occupancy grid maps, uncertain data processing and map update with bids information, which shows the consistency of the whole method. Moreover, we propose a new performance metric, called target point exchanged ratio, to reflect the degree of collaboration. The results of practical robot experiments and simulations demonstrate that the improved method is more efficient than the original market-based approach.3) For the problem of formation and coverage with failed or added robots of swarm robot, we propose a relay switched topology control for mobile robot networks in a theoretical and algorithmic level, which is a novel view of relationship between individuals and the whole system to deal with coverage problem, and becomes a theoretical frame of coopration coverage for large scale of mobile robot systems. Based on the graph and complex network theories, we establish the model of a mobile robot network which combines switched network topologies with an interaction dynamic model for describing the motion of the robots. Correspondingly, the control method is also divided into two levels: in the topology level, we analyze the effect of failed robots and added ones upon the network topology, and propose a relay switched topology control with self-healing ability and scalability; in the individual level, we transform the topology control into individual control algorithm with local interactions. We propose a set of metrics to evaluate control methods, including connectivity, convergence, self-healing ability, scalability, robustness and stability. We show that the proposed algorithm can prevent the network topology from being separated into two or more disconnected parts, and maintain the performance of the network. Based on the Lyapunov exponent, we further provide a criterion of the stability of the network with the proposed distributed control. Finally, we demonstrate the advantages of our method by performing simulations of formation and coverage. The advantages of our approaches over other methods are presented which include lower recovery time, lower power-consumption, more robust against communication failure, and zero blind zones for the coverage task.更多还原