Józef Winkowski

A Model of Evolving Relational Structures

929

Abstract

A model of evolving relational structures and its application to plan-formation are proposed.

Evolving relational structures are systems whose potential states are relational structures. They can be represented by contextual Petri nets whose state elements reflect relations among elements of the respective relational structures and transition elements reflect how such relations can change. Making use of contextual Petri nets instead of standard ones allows one to regard as concurrent also changes that depend on not necessarily disjoint contexts.

Plan-formation problem consists in finding in a finite set of available actions on relational structures a sequence of actions that would lead from a finite initial relational structure to a finite goal relational structure. Application of the model to this problem consists in defining a finite evolving relational structure that represents the potential sequences of actions, in formulating the problem of finding a sequence as required as a collection of linear programming problems, and in solving the problems thus obtained.

Keywords : relational structure, contextual Petri net, evolving relational structure, contextual occurrence net, branching process, configuration, history, cut, plan-formation problem, linear programming.