Answer Set Programming for 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.