交互计算模型中的时间意识和主动性

理论计算机科学电子笔记141（2005）69-95www.elsevier.com/locate/entcs交互计算模型中的时间意识和主动性Leo Motus1塔林技术大学19086爱沙尼亚梅里克·梅里斯特Tartu University Institute of Technology50411 Tartu，Estonia沃尔特·多施吕贝克大学软件技术学院Luebec，德国摘要本文讨论了明确的属性和需要验证的需求，这些属性和需求是由环境和用户强加给软件密集型系统的。这些系统对时间要求严格，可能包含自主组件，并可能表现出主动行为。 建议在 软件密集型系统中的属性分析和验证需要交互式计算的时间感知模型。 这篇论文的作者声称，迄今为止使用的时间解释，在计算机科学中，时间计数系统过于简单，而几个同时维护的独立时间计数系统是对交互作用进行时间分析的必要前提。提出了一个比较现有交互计算方法的特征空间，并讨论了交互计算时间感知模型关键词：主动和自主计算，时间意识，时间敏感的相互作用，许多同时度量时间，交互式计算模型分类的特征空间。1电子邮件：Leo. dcc.ttu.ee1571-0661 © 2005 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.05.01770L. Motus等人理论计算机科学电子笔记141（2005）691介绍当代计算系统的实际设计已经脱离了基于Church-Turing算法理论的传统方法。从实用的角度来看，新系统越来越多地由组件（重用或专门开发）构建，并且越来越多的新计算系统直接与其（非计算机）环境以及其他计算系统交互。从哲学的观点来看，新的实践扩大了不完全信息对组件属性和环境的影响即使在极少数情况下，当存在关于自然和/或人工环境的完整知识时，人们也不能利用它，因为有限的计算能力与环境所施加的要求不匹配。例如，考虑调聚反应的控制，其中反应的实际生产持续时间短于求解动力学方程所需的时间，所述动力学方程确定给定条件下的反应组件的使用部分地将设计者的注意力从算法转移到算法（及其集合）的交互上。这是因为任何组件都可能包含一种以上的算法，而组件中使用的算法的精确描述和组件的内部结构很少为设计者所知。内部结构不同的部件往往从算法到算法交互的兴趣转移已经引发了对以交互为中心的计算模型的研究（参见，例如，[22，45，47]）。计算系统与其环境的直接交互意味着违反了在基于传统算法理论的计算中广泛使用的许多传统假设。这些侵权行为的一些例子是：• 非终止（即持续）计算已经成为一种规则，而不是例外（如在数据处理中）;换句话说，领先的计算范式已经从字符串处理转移到流处理;• 非干扰假设是算法并行计算的可验证性所必需的，但不适用于强制并发计算模式;强制并发是由计算系统的环境[24，26]强加给计算系统的，通常是流处理的结果• 由于计算系统开始直接与其环境交互，计算的上下文感知已经成为一个问题;在许多情况下，上下文感知可以被简化为计算的时间感知和位置感知，和/或组件的交互;在这种情况L. Motus等人理论计算机科学电子笔记141（2005）6971在学习和/或适应系统的过程中，还应该考虑计算和环境历史作为定义动态环境的特征之一。传统上，这些问题已经被研究用于构建嵌入式实时系统、普适计算系统和通用即插即用系统的理论基础，这些系统通常以移动组件的存在、组件间交互的动态变化拓扑、来自环境的强干扰以及来自其用户的相当严格的依赖性要求为特征。实际计算系统的发展已经将上下文感知问题转移到计算的形式化描述（计算模型）中1.1组件，主动性，代理和紧急行为当代计算系统是由组件构建的-汽车中的控制和监控系统，通信系统，运输和银行系统的许多基本功能，以及医疗设备，计算模型只是几个例子。所有这些计算设备和系统是由自主组件（通常来自COTS（商用或商用））构建的，并且本质上是软件密集型的。 软件密集型设备的基本功能软件密集型系统与其他工程系统的不同之处在于，它们的功能可以很容易地修改，它们显然更有能力进行明确的主动行为，并且与非软件密集型系统相比，它们更经常地依赖于动态演变的控制结构。本文作者所说的主动性是指构件参与其环境演化的能力，选择目标导向的活动，以更好地满足构件的目标，并且在一个设计良好的系统，以更好地满足系统的目标。通常主动性增加了组件的自主操作能力。主动行为的概念源于自然世界，并首先被分布式人工智能、人工生活和计算机控制社区应用于人工世界的人工制品。大多数软件密集型系统跨越自然和人工世界的边界运行- 例如，用于技术设备和技术过程的计算机控制系统、医疗设备、用于生境监测的系统、自主移动机器人、交互式问题解决系统-并且通常包含基于AI的组件。考虑到软件设计的主要趋势--72L. Motus等人理论计算机科学电子笔记141（2005）69软件密集型系统。具有自主和主动行为的组件的使用迅速增加是当今计算机应用中非常明显的趋势。具有自主和主动行为的组件与代理的许多定义相匹配，例如，[35]。Agent和由Agent构建的系统（多Agent系统）本身就是一个成功的研究和应用领域。然而，在计算上，应用主动组件和多代理系统的软件密集型系统（和设备）面临非常相似的理论问题。在更大的范围内，这可以被认为是生物学和/或分子生物学中获得的知识与新兴的人工科学交叉受精的例子[37]。这种方法被称为动态工程。这个名字是由J. Ferber在分布式人工智能研究的背景下创造的，并表示通过应用交互作用的自主和主动组件来开发人工系统的过程[9]。与基因工程的相似性，如对自然生物系统的定义，是有意的，并强调与生物系统相比，主动人工系统的构建原则之间的某些凝聚力。多智能体系统基本上依赖于行为特征，这些特征在传统算法计算中无法指定，但不可避免地存在于实时，自治和/或主动计算系统中。这些特征的例子是计算的持久性、计算系统与其环境之间的直接交互、对时间的感知、交互的动态演化结构以及涌现行为的显著份额。在用户需求规范和设计阶段，这些属性无法完全预先指定。这些属性的外观取决于计算系统本身的操作中的事件的特定上下文和历史，以及系统环境中的事件的上下文和历史试图在算法计算的范例内处理和分析上述特征导致了理论上的困难[3，18，22，23，45，47]。涌现行为主要是在自然系统中研究的。P.W. Anderson在[1]中指出，“复杂系统的行为不能简单地通过对其组成部分、元素和实体的性质进行外推来理解”。安德森米尔纳发表了[22]，这是第二波对以相互作用为中心的计算模型感兴趣的第一篇论文之一随着计算机系统中组件数量（及其主动性）的增加，以及实际应用中软件密集型系统的数量，涌现行为在人工系统中的作用已成为一个重要的实际问题。L. Motus等人理论计算机科学电子笔记141（2005）6973问题.这是搜索新的计算范例的额外论据，因为传统的范例（基于Church-Turing算法理论）实际上忽略了所设计的计算系统的涌现行为。计算机科学的发展逐渐达到交互式计算的支持者所制定的理解如下：“诸如由UML建模的交互式系统代表了一种新的计算范式，它本质上不能使用传统的或算法的工具建模。 新计算范式的核心是这样一个概念，即系统的工作不是将单个静态输入转换为输出，而是提供持续的服务。1.2软件密集型系统新的计算范式（以交互为中心的计算模型）的开发和阐述进展顺利，并迅速流行起来。然而，到目前为止，计算的上下文感知还没有得到足够的关注。自从计算系统开始与其环境直接交互以来，上下文感知就成为了一个问题，特别是在计算系统响应于环境状态的改变而修改环境的行为或修改其自身的功能的情况下。实时、嵌入式系统以及监视和/或诊断系统是上下文感知计算系统的典型示例。上下文感知的精确定义取决于特定类别的应用程序。记住当代计算机的应用例如控制、监视、监视、通信、决策系统，这些系统由自主的、主动的和移动的组件构建，是高度分布式的，并且通常依赖于异构的自组织网络--在更复杂的情况下-涉及机器学习，适应和自组织-计算系统的组件的环境感知成为上下文的重要元素。为了能够分析上下文感知计算系统的行为，应该将环境视为可分析系统的一部分。环境也被描述为一个更大实体的交互、潜在主动和自主组件的集合。本文主要讨论计算系统的时间感知特性，并将位置感知和环境感知的讨论推迟到后面的文章中。之所以做出这个决定，不仅是因为时间约束计算系统已经研究了一段时间74L. Motus等人理论计算机科学电子笔记141（2005）69但主要是因为当代计算应用中所需的时间意识在理论上是一个真正具有挑战性的问题，参见例如[29，36]。在计算中，时间总是以运算的拓扑顺序的形式存在。随着多道程序设计和多处理器的出现，关键算法的执行时间和激活时刻的性能和调度问题变得越来越重要，相关的调度理论将度量时间引入到计算中。引入时序逻辑来描述和分析程序的某些性质，扩展了单一度量时间的应用范围。许多建模领域也应用单一度量时间（例如计算经济）。通常，在这些应用中，度量时间应用完全可逆时间概念或严格递增时间概念。一些时间逻辑使用“分支时间”的概念哲学家区分了三个通常不同时使用的公制时间概念（例如，见[6]）• 严格递增的度量时间（例如，应用于生物学）• 完全可逆的度量时间（如应用于理论物理学）• 具有移动原点的相对度量时间（例如在心理学中的应用）。为了能够捕获所有所需的特征，同时应用所有三个度量时间概念的少数例子之一是实时系统中组件间交互的时序正确性分析，如[25]中首次提出的，并在[29]中进行了细化传统上，研究人员描述所研究的现象，系统的设计者从他/她的角度描述正在开发的系统，假设完全控制情况。因此，设计者和/或研究者的时间足以捕捉现象或系统的动态。然而，在由前摄辅助部件组成的系统中，每个部件可以具有其自己的独立时间计数系统。因此，整个系统的一个额外的时间维度不能解决时间意识问题。这甚至更是如此，因为在许多情况下，研究人员和/或设计人员并不能完全控制情况计算系统的许多实际应用接受自主和主动组件作为计算系统的构建块，允许这些组件与环境的直接交互，并且要求L. Motus等人理论计算机科学电子笔记141（2005）6975计算系统是分布式的。因此，研究者不得不承认在由（分布式）计算系统及其环境构成的复合体中存在多个独立的时间计数系统，这些时间计数系统将被同时维护。当然，人们可以争论是否所有这些计时系统都必须被明确考虑。嵌入式实时系统的现有经验表明，为了分析强制并发操作的特性，必须同时维护几个独立的计时系统，以便验证组件间相互作用的正确计时[26，29]。每当作者在本文中进一步提到时间感知的以交互为中心的计算模型时，都假设相应的时间模型包括多个独立的度量时间，每个时间的多个概念同时存在。现有的软件工程实践，以及用于开发基于组件和/或基于代理的软件的相应工具，支持简单的时间模型，不促进组件间（和代理间）交互的时序分析。事实上，目前广泛使用的时间模型只考虑了时间和调度的特点，而忽略了交互的时间性本文作者建议，进一步的研究应集中在潜在的方法，设计，组装和分析的计算系统的基础上自治，主动组件。在大量的应用中，重要的是，新的理论和方法明确地关注于组件内和组件间交互的描述和分析，并特别支持对计算系统施加的上下文感知需求的可验证的满足。可以指出两个互补的研究目标• 如何建立一个系统，保证所需的行为，使和评估紧急行为，并尽量减少不必要的行为（“传统”的研究领域以交互为中心的• 如何构建一个系统，第一个目标可以与第二个目标分开实现，而第二个目标不能与第一个目标分开实现。这意味着，为了设计和构建计算系统，并分析其上下文感知相关属性，需要上下文感知交互计算的理论，以及相应的计算模型。一个自然的hy-76L. Motus等人理论计算机科学电子笔记141（2005）69假设是上下文感知交互计算的理论应该“无缝地”集成1.3关于本文本文提出了一种研究的问题，试图整合传统的和上下文感知的交互式计算的理论。本文的第2节比较了嵌入式实时系统与时间约束多智能体系统的特性，并提出了一个通用的范式，用于推理这些上下文感知交互式计算系统的计算特性。第3节调查的一些想法和概念，导致明确制定的本质互动计算，并最终到几个原型的互动为中心的计算模型。第4节提出了一个特征空间，该特征空间使得能够比较在不同应用中操作并且必须满足以下条件的计算系统：广泛的需求-例如，数据处理，信息处理，计算机控制，在线监控，决策支持和多代理系统。第5节讨论了一种潜在的方法，通过扩展Q模型与时间流处理方法来开发一个时间感知的，以交互为中心的计算模型。2基于组件和代理的系统推理寻求有效的信息表示和封装方法，以实现自然的软件结构，一直是软件工程的驱动力。信息封装方法的演变是从模块化编程开始的，随后是面向对象的编程和设计，最终到达基于组件的软件时代。组件通常但不一定总是具有有限自主性的对象的集合，即组件可以存在，并且在一定程度上以独立模式操作。为了全面运行，组件通常需要特定的支持基础设施。面向对象编程的实践一直（直观地）遵循交互式计算的范式。尽管如此，对象始终只能部分控制自己的方法和数据结构。一个自主的对象（或者更确切地说是一组这样的对象）对自己的方法有完全的控制，形成了实现代理的实用基础。在现实中，一个实现的代理需要一个动态的支持基础设施，其全面的自主操作。 在这里，全面自主操作意味着代理L. Motus等人理论计算机科学电子笔记141（2005）6977并选择行动，以确保满足时间和其他约束强加给其自主行为的环境[10]。在传统的研究方法中，人们的注意力通常集中在与智能体的智能相关的问题上，如推理、信念、意图、愿望、与其他智能体的谈判等。换句话说，多智能体系统的研究主要是以智能体为中心的，甚至系统的组织方面也是通过智能体的“心理”状态来描述和实现的分布式人工智能研究中的计算和系统工程问题受到的关注相对较少。在实时系统（和嵌入式系统）领域的研究重点一直是控制，监控和通信问题，重点放在系统工程方面。信息封装是最重要的，基于组件的设计被广泛使用。然而，计算方面获得的关注稍少-注意与代理的类比。人工智能方法越来越多地应用于实时嵌入式系统中，在许多情况下，实时系统的某些组件是代理。 在实际应用中，一个非常明显的趋势是两个领域的合并-其结果是，多代理系统的基础设施是一个复杂的时间模型，除了多个，潜在的独立的时间模型在个别代理增强。 与此同时，一个实时系统是由自主的，主动的组件扩展。因此，实时系统被认为是松散耦合的集合互动的自主代理（和其他组件）与时间关键的约束代理（和代理（实时系统的组件）和它们的交互模式可以在集成、测试期间以及在系统的正常操作期间动态地改变-例如，由于代理的自主、主动行为，或者由于代理的移动性。在传统的实时系统中，组件的受控动态重构一直是期望的，但为了增加行为确定性，故意避免了这种重构。换句话说，固定结构的应用只是为了能够在设计过程中以合理的信心预测未来系统的行为。基于组件的设计以及组件不断提高的自主性和主动性使实时系统具有自动重构能力，并将实时系统中涌现行为的比例提高到需要重新考虑行为分析方法的水平。一个典型的基于代理的实时系统运行在一个时间敏感的环境中，78L. Motus等人理论计算机科学电子笔记141（2005）69与传统的实时系统相比，它具有一个主要的附加属性-交互代理的完整列表及其交互结构不能在设计阶段最终确定。这一特性至少引发了两个新的研究课题。首先，基于代理的架构本身是不断发展的时间和不断发展的架构的不同方面需要监控（可能是部分控制），以保证所需的服务，并避免不必要的紧急行为。第二，实时系统的研究，由自治代理与强加的时间和位置约束的代理的简而言之，我们需要一个计算系统的计算模型，通常：• 分布在动态可重构的异构计算机网络中，该网络包括有线网络、无线网络和具有潜在移动节点的多跳自组织• 立即与人工和/或自然环境• 包含具有环境感知能力的（智能）组件，可实现自主和主动行为• 提供持续不断的服务，支持算法并发，以及在[26，45]• 具有一个逻辑结构，该逻辑结构可以被描述为一个松散耦合的、上下文感知的、交互的代理的集合，这些代理满足由环境和它们的交互伙伴所施加的所有行为要求和约束。3计算的新概念和计算模型计算新概念的出现普适计算是基于应用于实时系统和即插即用实验的原理的扩展。计算上的新概念已经从与自主计算[16]和主动计算[39]相关的普适计算领域中出现。这两个新概念在某种意义上是相关的，即系统中自治组件的存在是向系统引入主动性特征自主和主动计算已经成为L. Motus等人理论计算机科学电子笔记141（2005）6979比较[41]。代理和基于代理的系统形成了自主和主动计算的一般示例。一个表现出主动行为的系统必须具有自主和主动的组件。每个自主组件可以具有其自己的独立计时系统。那些表现出主动性的组件必须有一个与目标处理子组件协作的感知子组件。如果几个主动组件为了达到更好的感知而形成联盟，情况会进一步复杂化。关于主动性的更详细讨论需要单独出版。考虑到时间问题，每个自主组件可以具有其自己的时间计数系统，并且那些时间计数系统中的每一个可以应用其自己的度量。严格地说，在不同的时间计数系统（时间模型）中定义的时刻和间隔只能在已知的不确定性范围内进行比较。因此，整个计算系统时间在代理通常被认为与计算机科学的传统一致，即时间是一个额外的维度的状态空间-这意味着一个单一的时间变量被引入整个系统。计算机科学中使用的传统时间模型的例子在[20，50]中进行了讨论和需要许多度量时间来描述计算系统及其环境的联合操作的主要原因是某些组件的自治性。在许多情况下，组件的自主性还意味着计算系统及其设计者没有或不能访问关于自主组件的内部操作的完整知识。例如，组件通过动态创建的通信链路直接相互交互（例如，由于系统自主和主动计算的正式计算方面尚未得到彻底的研究。直觉上，我们相信一个合适的计算基础模型应该是交互式计算。对于许多应用程序的交互式计算模型，应扩展与时间意识。不幸的是，这样一个模型的适当的和广泛接受的形式主义还没有。进一步在本文中，试图走向时间感知模型的交互式计算。80L. Motus等人理论计算机科学电子笔记141（2005）69计算模型一个计算模型提供了一个简明的（原则上，近似匹配的）描述在计算系统中发生了什么[3，46]。图灵机的概念提供了计算的非常精确和广泛接受的描述。然而，今天的计算系统的许多属性不能用图灵机的概念（以及源于Church-Turing论文的算法理论）来处理。图灵后三台机器被遗忘了一段时间，因为它不适合主流计算。在20世纪60年代末H. A.西蒙在他关于人工科学的论文中（例如，见这些论文的第三版[37]），强调了计算在两种不同环境边界上的重要性。这样的计算很好地对应于c机和o机的思想。计算机和驻留在潜在不同环境中的其他实体之间的交互被认为是C-和O-机器的基本属性在1970年代末，西蒙几乎在同一时间，第一个描述具有显式交互的时间感知、强制并发、分布式计算系统的方法[34]发表了，不幸的是，多年来一直没有被注意到。自20世纪90年代以来，交互式计算得到了普及。实际计算的角色逐渐变化，以及对计算本质的更好和更自由的理解，导致了交互计算的概念，理论和模型的发展，例如[23，42，43，47]。最近的研究论文从根本上放宽了Church-Turing算法理论的严格和传统的限制。其中一些概念假设了丘奇-图灵意义上的可计算性的根本概括，例如[14]定义了可计算性逻辑，其中计算被描述为机器与环境的游戏。其他一些人建议采用系统的逐步方法（例如[12]），最终也会导致丘奇-图灵命题的非平凡概括。从CCS [22]开始，量化时间已经从交互式计算中抽象出来。米尔纳WegnerL. Motus等人理论计算机科学电子笔记141（2005）6981交互式计算，再次忽略了明确的定量时间。本文的作者相信，需要交互式计算的时间感知（或上下文感知）模型来推理其属性的交互式计算系统的份额正在迅速增加。相关哲学问题计算的发展不断增加了不确定性在计算中的作用。在Church-Turing算法理论的框架中，因果关系的完全知识的假设是必要的，并且通过禁止在算法执行期间来自环境或来自其他算法的干扰而被进一步放大。在今天的计算系统中让我们考虑一个嵌入式实时系统或多智能体系统的例子互动应该是持续的，而不是终止的，通常来自自然世界的合作伙伴是控制（或至少平等）的合作伙伴。后一种性质通常可能导致对计算系统中的算法的执行的计算系统中的交互伙伴通常是专门设计的，或选择与自然（或人工）世界中的特定组件一起工作我们有理由期望相互作用的伙伴的动态特性是匹配的。在实践中，如果一个合作伙伴对另一个合作伙伴的行为施加时间限制，则可以匹配相互作用的合作伙伴的动态特性上述干扰情况对应于违反科学中的基本假设这种类型的违反可以通过引入时间约束来避免，该时间约束明确定义了固定公理基假设成立的域。时间限制的另一个有用的作用是近似表示未知（或不完全知道，或物理上无法访问的知识）的因果关系。想象一下，例如，一个计算机控制的调聚反应，其中有用产物的增加在达到一定浓度后减慢。停止反应的合理点原则上可以基于该反应的动力学方程组来计算。但是，计算停止点所需的时间比82L. Motus等人理论计算机科学电子笔记141（2005）69反应才能达到这个地步。在实践中，可以用反应的生产阶段的估计持续时间来尽管时间关键和/或时间和位置感知的计算机应用程序迅速增加，大多数研究人员仍然以简单的方式考虑时间的作用-作为一个单一的变量，常见于系统中使用的这种做法源于数学，并且仍然是计算机科学的主导信仰。假设这种信念是基于这样的假设，即一个中立的观察者（例如系统的研究人员或设计者）可以完全了解所研究的现象，并且可以观察到该现象或所设计的系统的所有细节。反过来，这个假设显然是由于对牛顿（一个观察者）和爱因斯坦（几个独立观察者）关于宇宙的理论的哲学基础的不完全正确的解释。本文第二节末尾所述的描述和分析计算系统的性质需要许多度规时间，这与量子理论中所在量子理论中，宇宙被认为是一个相互作用的自治粒子的集合，这些粒子都同样重要。即使是观察者，如果他们存在的话，也不比其他粒子更重要，更有能力。在这样的宇宙中，每个粒子都有自己的时间计数系统，这个系统可以独立于其他粒子的系统，这一说法来自Simon [37]和Wegner [44]提出的观点交互式计算以下是一个相当主观的关于交互式计算范式的演变以及用时间意识扩展它的方法的出版物分组列表：• 关注状态转换视图的状态机：输入对状态更新和输出c机的影响[40];自复制自动机[32];抽象状态机[13];输入/输出自动机[9];属性自动机[21];交互机[43];• 过程代数：例如，由CCS [22]和π-演算[23]表示;成本演算（用于交互式问题解决的有界理性代理的过程代数）[47];• 基于流的方法：时间感知历史转换器[5];交互系统的组成细化[4]，[7];L. Motus等人理论计算机科学电子笔记141（2005）6983• 基于逻辑框架的模型：以弱二阶时间预测演算为代表[18];时态逻辑[20];理性代理逻辑[48];计算逻辑[14];• 其他方法：以Quirk的报告[ 34 ]，Q模型[ 26 ]和代理群体角色模型[ 10 ]为代表上面列出的出版物，连同新的，实际的计算系统的有趣的属性，形成了计算模型的分类选择的特征空间的维度的基础。在一个精心选择的特征空间中进行分类是为了支持各种方法和途径的比较，以走向交互计算的时间感知模型。在本文中，我们建议的通用分类法，隐含地包括所有上述列出的出版物。在特征空间中明确定位不同方法的详细分类法的发展需要一个单独的分类，这不是本文的目标4计算分类的特征空间为了在开发时间感知的以交互为中心的模型方面取得系统的进展，需要根据它们的特征对各种计算模型进行分类其他研究人员早期使用的特征空间的例子已经在[3，33，45]中进行了调查和讨论。特征空间应将不同的计算模型分散在空间中，并将相似的模型聚集到空间中的簇中。早期用于分类的特征空间维度不能明确强调上下文感知的主动计算系统的特定属性。因此，我们建议特征空间- 此外，我们证明，这个特征空间清楚地区分了传统的基于Church-Turing算法理论的计算模型，交互式计算模型，以及上下文感知的交互式计算模型。特征空间的维度解释如下：• 动作表示计算系统的结构单元的执行，其包括输入信号（消息）的消耗，并且导致产生该单元的输出信号（或消息），该输出信号（或消息）可以影响其他结构单元或环境的行为;结构单元可以是算法、组件或代理。• 交互表示将信号（消息）从该信号（消息）的生产者传输到消费者的过程;生产者和消费者通常是计算系统的结构单元，或其引擎。84L. Motus等人理论计算机科学电子笔记141（2005）69Fig. 1. 特征空间及其投影。删除;在某些情况下，信息可能在传输过程中被故意修改（例如，出于可靠性、安全性或保密性原因）• 时间感知特性描述了系统中使用的时间模型-从单个拓扑开始（即，非度量）时间，然后是拓扑时间和一个度量时间，以及具有拓扑时间和若干度量时间的最复杂情况;在某些情况下，还需要区分单一时间概念的使用者（例如可逆度量时间）或几个同时时间概念（例如可逆的、严格增加的和具有相同度量的相对时间）。特征空间在二维平面上的投影（见图1）交互式动作、时间感知动作和时间感知交互的平面相当精确地描 述 了 已 经 存 在 的 研 究 方 向 （ 例如 交 互 式 计 算 、 时 间 约 束 计 算 和 交 互 的 定 时 分 析 ） 。直观地说，三维特征空间形成了一个很好的起点，用于建立现有方法的分类，并讨论开发计算模型的潜在新方向，对于每个特征，将通过标记引入度量，这些标记基于定性属性来定义模型的类别，这些定性属性对于区分计算模型很有意义。如果需要更详细的分类，标记物的数量可以增加。本文中考虑的类别不是不相交的，通常，离坐标原点较远的类别包括离坐标原点较近的类别的属性。相互作用行动时间感知动作时间意识交互动作L. Motus等人理论计算机科学电子笔记141（2005）6985坐标在本文中，我们将考虑以下类作为起点。操作维由以下标记划分：• A1执行动作的结构单元包括固定的算法，这些算法之间存在因果关系，并且在动作过程中环境可能不影响算法及其关系;在控制理论中，这种情况称为程序控制。• A2系统中某些结构单元的行为在动作过程中直接受到环境的影响或控制，或间接受到先前动作的影响;在控制理论中，这种情况称为反馈控制。• A3-系统的一些结构单元的行为是主动和自主的，这意味着单元可以从一组动作中选择一个动作，在给定的情况下最好地服务于组件（具有动态变化行为的智能和自我组件）。• A4-除了主动性之外，一些组件还能够根据不断变化的条件学习和调整其行为和目标（具有高比例的紧急行为和难以预测的动态行为的系统）。交互作用维由以下标记划分• I1结构单元之间的相互作用是由算法（因果原因）严格预先定义的，不能动态修改;传统的并行处理，作为算法计算的一个例子，属于这一类。• I2在不同的情况下，系统可以有不同的行为，并且结构单元之间的相互作用实际上决定了系统的行为（例如，不同的算法可以产生系统的等效行为）;这是交互式计算的情况;在这种系统中可以接受流处理和强制并行处理86L. Motus等人理论计算机科学电子笔记141（2005）69• I3-这一类别包括基本上基于时间约束交互计算的系统模型，包括对交互发生时刻和在这些交互期间交换的信息的有效性施加的约束。时间感知维度由以下标记划分：• T1有时拓扑时间也称为逻辑时间。时间是通过对系统中发生的事件（对我们来说很重要的事件）进行排序而建立的，而不关注事件发生的时刻与度量时间的相应时刻之间的显式关系。 计数事件是一个很好的例子这样的时间很容易使用在顺序程序中，而在并行程序和具有分布式处理的程序中，事件的排序变得复杂。• T2这是模型和系统的类别，其中除了拓扑时间之外，还有度量时间（一个严格周期性滴答的计数器，可以与人类使用的天文时间同步）。周期性滴答的计数器基于该计数器，系统设计者可以构建使得能够使用可逆时间（即，偶尔回到历史中，重做事情）或相对时间来推理该系统中的属性的定时器。严格递增、可逆和相对时间（由应用相同度量的不同计时器测量）被称为时间概念[6]。• T3此类别包含接受自主和主动组件作为构建块并允许这些组件与环境直接交互因此，研究人员不得不承认存在多个独立的时间计数系统，这些系统将在由（分布式）计算系统及其环境形成的复杂系统中同时维护。通过独立的时间计数系统，作者指的是不同的度量时间（即具有不同度量的周期性滴答计数器）对于这些度量时间中的每一个，系统可以维持若干同时的时间概念。上面介绍的标记物用于fea的划分L. Motus等人理论计算机科学电子笔记141（2005）6987相互作用I3传统模式计算I2I1A1 A2 A3A4T1行动T2T3时间意识图二、带有标记的特征空间图2中的真实空间。作为说明，在坐标原点附近显示包括根据Church-Turing算法理论描述计算的计算模型的类别。这个类别是在算法描述的动作（A1）与算法预定义的相互作用（I1）的子空间中，并且在单一拓扑时间（T1）下。请注意，使用时态逻辑的模型不属于这个子空间，因为它们中的许多都是用度量时间操作的据我们所知，在这样一个特征空间中，计算模型的定义分类尚不可用。不同特征空间中计算模型的分类已经在[33，50]中讨论过。初步结果表明，基于本文定义的特征的分类是一个有价值的工具，用于规划研究，正式描述和分析新兴的计算范式。图3显示了传统计算模型、交互机器和时间感知交互机器的相对放置的一般视图。可以开发出更详细的分类法来区分特定的形式主义所建议的特征空间源于快速扩展的新类别的计算机应用的预期属性和要求-88L. Motus等人理论计算机科学电子笔记141（2005）69相互作用时间感知交互机器I3I2互动机器I1常规型号T1行动A4T2T3时间意识图三.示例分类法。选择产品-在实践中，这是一个选择适当产品的问题在标记中，太少的标记给出概括的图片，太详细的标记提供太复杂的图片。时间感知计算通常被认为是奇怪的东西，而不是真正属于体面的计算方法的家庭。这篇论文的作者对这个特征空间中模型的第一个初步分类感到鼓舞（见图3）-可以看出，时间意识被认为是算法计算的自然扩展。我们在KRATT环境[30，31]中逐步开发时间感知多智能体系统的交互式计算模型的经验支持分类法所建议的印象。图3中的分类法固定了用于算法计算的传统模型、用于交互式计算的模型和用于时间感知交互式计算的模型在这样一个通用的层次上，分类法几乎没有实际用途，但是如果使用相同的分类法来定位更具体的产品-以下部分将讨论Q模型在描述具有动态变化的配置和交互拓扑以及在其组件中具有时间感知的持续计算的计算系统中的使用A2 A3A1