没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记318(2015)53-68www.elsevier.com/locate/entcs群体适应行为的时空性能分析Cheng Feng1,2英国爱丁堡大学信息学院Marco Gribaudo3米兰理工大学电子、信息和生物工程学院意大利米兰Jane Hillston简·希尔斯顿1,4英国爱丁堡大学信息学院摘要许多系统,无论是自然的还是工程的,都表现出集体适应行为。自然的例子是成群的动物和昆虫,人造的例子包括群机器人和传感器网络。事实上,许多系统都有人类和基于信通技术的代理人在发挥作用,分布在一些地理区域:Milner定义的信息学环境。近年来,人们越来越感兴趣的建模这些系统,以了解其动态行为。在这里,我们考虑如何为这样的系统定义有用的性能度量的后续问题,基于对一个简单直观的例子的考虑。关键词:时空建模,性能建模,集体适应行为1引言表现出集体行为的系统有许多有趣的性质。来自自然界的例子,如成群的动物和昆虫,经常被研究1这项工作得到QUANTICOL项目600708的部分支持。2电子邮件:s1109873@sms.ed.ac.uk3电子邮件:marco. polimi.it4电子邮件:jane. ed.ac.ukhttp://dx.doi.org/10.1016/j.entcs.2015.10.0191571-0661/© 2015作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。54C. Feng et al. /Electronic Notes in Theoretical Computer Science 318(2015)53它们的突发行为,即在种群水平上变得明显但从所描述的个体行为中不容易明显的模式。在工程系统中,这种涌现的行为构成了系统的性能正在开发越来越大规模的、地理上分散的ICT系统,以各种方式支持人类的努力。 这可以被认为是实现的信息学环境预测米尔纳和韦泽[10,13]。这样的系统与人类代理几乎透明地与计算元素交互。例子包括智能城市应用,如智能交通,智能电网和许多现代汽车系统。在这些系统中,它们的透明度和普遍性意味着在部署之前从定性和定量的角度调查它们的行为也许比以往任何时候都更加重要。工作目前正在进行中,例如在QUANTICOL项目[6]中开发建模形式主义以捕获这些系统的行为[5,9]。在这里,我们开始一个补充调查类型的措施,可以从时空系统。传统的绩效衡量方法假设只有一个操作点。当行为有(有限的)空间方面时,状态注释通常用于在语法上区分不同的位置,并应用常规的性能测量。我们寻求采取一种更激进的方法来支持建模,在这种建模中,空间被明确建模,并在描述系统行为时充分利用。2领导者和追随者场景我们考虑一个简单的场景,其中代理在二维网格中移动,如图1所示。我们假设网格是有限的,边界是领导人福尔韦斯领导者之路图1.一、领导者和追随者的故事DminC. Feng et al. /Electronic Notes in Theoretical Computer Science 318(2015)5355这意味着我们考虑的是环面上的运动。每个智能体每次移动一步,每一步都可以向任何方向移动:北、东、南或西。我们假设有一个杰出的代理,领导者自主移动,在网格上执行随机行走任何其他代理都是追随者。追随者的目标是模仿领导者的运动。然而,有一个限制,即跟随者应该与领导者保持最小距离dmin,并且应该绝对避免碰撞。在下文中,我们考虑一些日益复杂的情况来说明我们的观点。特别是,该模型将在PALOMA中指定[5],一个新的进程代数,是专为空间分布的集体和自适应系统的建模。 在描述这些场景之前,我们首先给出一个PALOMA简介欲了解更多详情,请参阅感兴趣的读者至[5]。2.1PalomaPALOMA是一种新的随机过程代数,它允许表达由分布在空间上的代理群体组成的系统模型。在PALOMA中,每个智能体都是一个有限状态机,语言是保守的,在模型的演化过程中没有智能体被产生或破坏(尽管它们可以停止改变状态)。该语言有两个级别的语法:X(l)::=!(α,r).XJ(lJ)|什么?(α,p).XJ(lJ)|X(l)+X(l)P::= X(l)|PP代理由位置参数化,这里用l表示。代理可以采取两种类型的行动,自发行动,表示!(α,r),和诱导的行动,表示?(α,p)。当一个智能体执行一个自发动作时,它以给定的速率r执行,该速率被视为指数分布的参数,其中1/r是动作的预期持续时间。自发行为被传播到整个系统,并且可以引起任何其他代理的变化,这些代理能够实现具有匹配类型α的诱导行为。 一个诱导动作有一个相关的概率p,它记录了主体对自发动作做出反应的概率相同类型的。 在广播系统的微积分[11]的风格中,这可以被认为是代理人倾听的概率,而不是简单地听到。替代行为由标准选择操作符表示,+.自发行动之间的选择是通过竞争政策,根据其相应的利率。我们假设在同一类型的诱导行为之间永远没有选择。一个模型P由若干个并行的代理组成。代理之间没有直接的通信,例如PEPA中的共享操作风格[7]。相反,所有的沟通/互动都是通过自发/诱导的行为。当一个动作在一个主体中被诱导时,它的影响程度由感知函数u(α,l,X,lJ,XJ)指定,其中α是动作类型,l和X是接收者主体的位置和状态,而lJ和XJ是发送者主体的位置和状态。这是另一个概率,给定位置,56C. Feng et al. /Electronic Notes in Theoretical Computer Science 318(2015)53在两个代理中,它们的当前状态和所涉及的动作类型决定了诱导动作发生的可能性。例如,当两个代理在彼此的通信半径r内时,感知函数可能具有值1,但是每当它们之间的距离大于r时,感知函数的值为0。显然,这给出了一组丰富的可能的交互样式,但请注意,每个具有诱导动作的智能体都独立地选择是否响应。2.2场景1:被动追随者在这种情况下,我们假设领导者可以选择以速率rrest休息,或者以速率rmv沿着随机方向移动一步。 此外,我们使用pn,ps,pw,pe分别表示向北,向南,向西和向东移动的概率。因此,Leader代理可以描述如下:L(x,y)::=(rest,rrest).L(x,y)+!(n,rmv pn).L(x,y+1)+!(s,rmv ps).L(x,y−1)+!(w,rmv pw).L(x−1,y)+!(e,rmv pe).L(x+1,y)在哪里!(rest,rrest)表示Leader以rrest的速率自发地休息,当它这样做时,它保持在当前位置。!(n,rmv pn)表示领导者通过以rmv×pn的速率进行自发动作n而向北移动一步。此外,我们假设跟随者只能被动地移动,通知他这样做因此,我们将追随者代理定义为:F(x,y)::=?(n,pl).F(x,y+1)+?(s,pl).F(x,y−1)+?(w,pl).F(x−1,y)+?(e,pl).F(x+1,y)其中,跟随者智能体可以通过诱导动作在一个方向上移动一步,并且pl编码跟随者响应领导者动作n、s、w和e的感知函数简单地定义为:u(n,l,X,lJ,XJ)=1u(s,l,X,lJ,XJ)=1u(w,l,X,lJ,XJ)=1u(e,l,X,lJ,XJ)=1这意味着,追随者将明确地看到命令从领袖2.3场景2:活跃的追随者在这种情况下,我们允许追随者更聪明一点。更具体地说,我们引入了一个内部时钟代理,它允许跟随者主动移动,而不仅仅是听领导者Clock代理简单地定义为:C. Feng et al. /Electronic Notes in Theoretical Computer Science 318(2015)5357⎪⎩i f((dist(l.x,l.y+1,L.x,L. y) dmin)((dist(l.x,l.y+1,L.x,L.y)> dist(l.x,l.y,L.x,L.y))最小值(l.x,l.y,L.x,L.y) dmin,b)dist(l.x,l.y +1,L.x,L.y) dmin)((dist(l.x,l.y+1,L.x,L.y)> dist(l.x,l.y,L.x,L.y))最小值(l.x,l.y,L.x,L.y)0⎧⎪⎨|首次访视(A1,l)-首次访视(A2,l)|如果a ge(A1,l)>0在移动中,跟随者不执行任何恢复动作的情况在开始时具有大的命中概率,并且随着时间的推移迅速降低。然而,这是由于领导者倾向于远离追随者,从而降低了命中概率。这在基于路线的移动情况下更加明显,其中命中概率为零,因为跟随者从一开始就开始失去领导者。在其他情况下,很明显,命中概率收敛到一个极限值,这是追随者行为的一个特征,并取决于他的参数。对于基于路线的移动,这仅在跟随者以非常高的速度作出反应的情况下观察到,因为这是唯一能够不丢失领导者的情况0.025 0.0120.020.0010.0150.010.0050.00080.00060.00040.000200200 400 600 800 1000 1200 1400 1600 1800 2000不0050100150200250300350400450 500不a)b)、见图7。不同时钟频率下领导者和追随者之间的命中概率:a)随机行走,b)领导者与路线。碰撞可以被概括为在最小距离dmin内:dist(F,L,t) dmin图10. 具有不同数量的跟随器的轮廓C(loc(L,t),n,t),其中dmin= 2。14结论和今后的工作在本文中,我们已经做了初步研究的措施,它可以是有趣的研究系统中,有时间和空间方面的行为的类型。这些是许多集体自适应系统(CAS)的重要特征,这些系统是由相互作用但自治的代理组成的地理分布系统我们已经说明了一个简单的领导者-追随者系统的想法,通过仿真研究在许多不同的情况下虽然我们的示例系统很简单,但强调可以从CAS模型中获得的丰富信息形式是足够的,并且很容易看出我们研究的措施如何适用于现实生活中的系统。例如,智能交通系统是CAS的示例[12],其中监管要求施加时空条件。公交运营商在频繁路线上受到车头时距要求的约束,这可以被视为我们的领导者-追随者情景的特殊情况。在这里,时刻表将扮演领导者的角色,而提供服务的公共汽车则是追随者。车头时距要求对跟随者的空间和时间分离施加条件,以确保为用户提供常规服务。在这种情况下,领导者的行为是确定性的,但追随者的行为,公共汽车,受到随机因素,如交通和天气条件以及人类互动。在未来的工作中,我们将进一步研究我们确定的措施,以了解它们与CAS的用户和操作员性能要求的匹配程度。在目前的工作中,我们从第一原则开始工作,评估我们简单场景中可用的数据另一种方法是使用时空逻辑来定义感兴趣的属性。在基于马尔可夫的性能模型的上下文中使用时序逻辑是成熟的[2],并得到PRISM等工具的支持[8]。空间逻辑也已研究多年[1],但据我们所知,尚未应用于CTMC的定量背景下,尽管最近的应用包括CAS的数据验证[4]。虽然在《逻辑学》中已经考虑过空间逻辑和时间逻辑的结合,但很少有正式的处理方法。视频序列分析中的一种非正式方法[3]。这里空间直到公式C. Feng et al. /Electronic Notes in Theoretical Computer Science 318(2015)5369与时间直到公式交错,以表达随着时间的推移图像中对象的相对位置的条件。在量化的时空逻辑中,我们会寻求为这些属性赋予一个值,就像概率与CSL中表达的时间属性相关联一样。引用[1] Aiello,M.,I. Pratt-Hartmann和J. van Benthem,编辑,[2] Baier,C.,B. R. Haverkort,H.赫尔曼斯和J. - P. Katoen,连续时间马尔可夫链,IEEE Trans.软件工程师29(2003),pp.524-541[3] Bimbo,A.D、E. Vicario和D.Zingoni,使用时空逻辑的图像序列的符号描述和可视化查询,IEEE Trans.知道。数据工程师7(1995),pp.609-622[4] Ciancia,V.,S. Gilmore,D. Latella,M. Loreti和M. Massink,集体自适应系统的数据验证:车辆位置数据的空间模型检查,在:第二届FoCAS集体自适应系统基础研讨会论文集,伦敦,英国,2014年,出现。[5] Feng,C.和j.Hillston,PALOMA:A process algebra for located markovian agents,11thInternational Conference on the Quantitative Evaluation of Systems(2014).[6] FET 主 动 FOCAS 项 目 600708 , QUANTICOL : 集 体 和 适 应 行 为 管 理 和 设 计 的 定 量 方 法 ,www.quanticol.eu。[7] Hillston,J.,“A Compositional Approach to Performance Modelling,” CUP,[8] Kwiatkowska,M. Z.,G. Norman和D. Parker,PRISM 4.0:概率实时系统的验证,在:计算机辅助验证-第23届国际会议,CAV 2011,Snowbird,UT,美国,2011年7月14日至20日。Proceedings,LectureNotes in Computer Science 6806(2011),pp. 585-591。[9] Latella,D.,M. Loreti,M. Massink和V. Senni,Stochemical基于定时谓词的自主计算通信原语,技术报告,QUANTICOL项目(2014)。[10] 米尔纳河,[11] Prasad,K.,A calculus of broadcasting systems,Science of Computer Programming25(1995),pp.285- 327[12] Reijsbergen,D.和S. Gilmore,使用车头时距数据对频繁公交服务的正式准时性分析,在:第11届欧洲性能工程研讨会论文集,佛罗伦萨,意大利,2014年,出现。[13] Weiser,M.,21世纪的计算机,Scienti fic American265(1991),pp.94比104
下载后可阅读完整内容,剩余1页未读,立即下载
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)