Answer Set Programming for Dynamic Domains

动态域的答案集编程

• 批准号: 445900505
• 负责人: Professor Dr. Torsten Schaub
• 金额: --
• 依托单位: Lehrstuhl für Wissensverarbeitung und Informationssysteme
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/445900505?language=en
• 关键词: Answer; Set; Programming; Dynamic; Domains

Knowledge representation and reasoning plays a key role in dealing with the fourth industrial revolution since it offers flexible and transparent ways for addressing complex problems. A prime candidate for solving knowledge-intense search and optimization problems, being widespread in production, storage, or workforce management, is Answer Set Programming. ASP, for short, is arule-based formalism for modeling and solving such problems. What makes ASP attractive is its combination of a declarative modeling language with highly effective solving engines. This allows us to concentrate on specifying a problem rather than programming the algorithm for solving. Although ASP experiences an increasing dissemination in academia and industry, a closer look reveals that this concerns mostly static or smaller dynamic domains. For example, ASP is highly competitive in static domains such as time tabling and workforce management, whereas it lags behind when it comes to substantial dynamic ones, as for instance, robotic intra-logistics that is about controlling a fleet of robotic vehicles roaming a warehouse to fulfill customer orders. Infact, there is still quite a chasm between ASP's level of development for addressing static and dynamic domains. This is because its modeling language as well as its solving machinery aim so far primarily at static knowledge, while dynamic knowledge is only indirectly dealt with via reductions to the static case.We address this challenge in the following way. We start from first principles by developing the logical foundations of our approach. We extend ASP's base logic with concepts from dynamic, metric and temporal logic by founding them on the common semantic structure of finite linear traces. In turn, we identify appropriate language fragments that are suitable for a modeling language fordynamic domains. We leverage the semantic principles for designing and implementing a novel solving technology supporting our temporal language. One of its cornerstones will be lazy constraint solving, since it allows us to to realize the temporal language constructs in an effective way with existing ASP systems such as our system CLINGO. Finally, we develop modeling and engineering techniques for applying our approach to industrial-scale scenarios. For this, we identified robotic intra-logistics as a perfect benchmark, since the problem is greatly dynamic, highly scalable, and combines an abundance of different aspects. This richness will not only enable us to develop a versatile approach to robotic intra-logistics but moreover extend ASP to a general purpose technology for dynamic domains.

知识表示和推理在应对第四次工业革命中发挥着关键作用，因为它为解决复杂问题提供了灵活和透明的方式。答案集编程是解决生产、存储或劳动力管理中普遍存在的知识密集型搜索和优化问题的首选方案。简而言之，ASP是一种基于规则的形式主义，用于建模和解决此类问题。ASP吸引人的地方在于它结合了声明性建模语言和高效的求解引擎。这使我们能够专注于指定问题，而不是编程算法来解决。虽然ASP在学术界和工业界得到了越来越广泛的传播，但仔细观察就会发现，这主要涉及静态或较小的动态领域。例如，在静态领域，如时间表和劳动力管理，ASP具有很强的竞争力，而在实质性的动态领域，例如，机器人内部物流，它落后于控制在仓库中漫游的机器人车队来履行客户订单。事实上，在处理静态和动态领域方面，ASP的开发水平之间仍有相当大的差距。这是因为到目前为止，它的建模语言和求解机制主要是针对静态知识，而动态知识只是通过对静态案例的约简来间接处理的。我们从基本原则开始，发展我们方法的逻辑基础。通过将动态逻辑、度量逻辑和时态逻辑的概念建立在有限线性迹的公共语义结构上，对ASP的基本逻辑进行了扩展。反过来，我们识别适合于动态领域的建模语言的适当语言片段。我们利用语义原理来设计和实现一种支持我们的时间语言的新的求解技术。它的基石之一将是延迟约束求解，因为它允许我们用现有的ASP系统(如我们的系统CLINGO)以一种有效的方式实现时态语言构造。最后，我们开发了将我们的方法应用于工业规模场景的建模和工程技术。为此，我们认为机器人内部物流是一个完美的基准，因为这个问题是非常动态的，高度可伸缩的，并且结合了大量不同的方面。这种丰富性不仅使我们能够开发一种通用的机器人内部物流方法，而且还可以将ASP扩展到动态领域的通用技术。