Implicit Boolean Network for Planning Actions
Авторы: Oparin G.A., Bogdanova V.G., Pashinin A.A.
Журнал: 45th Jubilee International Convention on Information, Communication and Electronic Technology, MIPRO 2022
Отчётный год: 2022
Аннотация: It is usual to classify the automated searching of a plan as an artificial intelligence problem. In planning, the environment is defined as a set of both states and transitions between them. Planning consists in searching for a finite transitions sequence (actions) that transfers the initial state to one of the states, satisfying the objective. As a model of the planning environment, we propose to use implicit Boolean networks - binary dynamic systems, the transition function of which is defined by the implicit Boolean equation relative to the current state variables vector and some subsequent variables vectors. For this model, the forming of a plan is reduced to qualitative analysis of dynamic properties of the implicit binary dynamic system. In particular, these are reachability or cyclicity properties over a given discrete time interval. At the final stage of this method, the verification of the Boolean formula satisfiability is performed. This formula includes the equation of the dynamics of the implicit Boolean network and the specification of the dynamical property being verified. The considered approach is demonstrated on the problem of planning a river crossing and constructing a Hamiltonian cycle in a graph. A specialized parallel algorithm for solving deeply structured Boolean satisfiability problems is proposed, which provides scalability with an increase in their dimension.
Индексируется WOS: 0
Индексируется Scopus: 1
Индексируется РИНЦ: 0
Публикация в печати: 0
Добавил в систему: