Answer Set Programming for Dynamic Domains

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

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.