Towards a solution to a plan-formation problem

• Autorzy: Winkowski J.

Warianty tytułu

PL

Zarys pewnej metody planowania akcji

• Języki publikacji: EN

Abstrakty

EN

The paper deals with the problem of achieving a goal in a system in which certain actions can be executed. The initial state and the states that may be reached from this state by executing actions are represented by sets of sente nces, each sentence saying that some objects are or are not in a relation. Available actions are represented as instances of rewriting rules. The problem consists in finding a sequence of actions that leads from the initia l state to a state in which the goal is achieved. The presented solution to this problem for a class of systems is based on reducing it to the problem of reachability in contextual Petri nets.

PL

Praca dotyczy problemu osiągania celu w systemie, w którym można wykonywać pewne akcje. Stan początkowy i stany, które moga być z tego stanu osiągnięte przez wykohnywanire akcji, są reprezentowane przez zbiory zadań, z których każde orzeka, że pewne obiekty są lub nie są w pewnych relacjach. Możliwe akcje sa reprezentowane jako instancje pewnych reguł przekształcania. Problem polega na znalezieniu ciągu akcji prowadzącego ze stanu początkowego do stanu, w którym cel jest osiągnięty. Proponowane rozwiązanie tego problemu dla pewnej klasy systemów polega na jego redukowaniu do problemu osiągalności w kontekstowych sieciach Petriego.

Słowa kluczowe

EN

system; state; action; goal; literal; situation; rewriting rules; relation rewriting system; safe rewriting system; contextual net; safe contextual net; net morphism; contextual occurence net; process; reachability

PL

system; stan; akcja; cel; literał; sytuacja; reguła przekształcania; relacyjny system przekształcania; bezpieczny system przekształcania; sieć kontekstowa; bezpieczna sieć kontekstowa; morfizm sieci; kontekstowa sieć wystąpień; proces; osiągalność

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2002
• Tom: Nr 948
• Strony: 1--18
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Winkowski J.

• Instytut Podstaw Informatyki PAN, Ordona 21, 01-237 Warszawa,

Bibliografia

• [Drum 89] Drummond, M., Situated Control Rules, in Proc. of the First Int. Conf. on Principles of Knowledge Representation and Reasonning, Toronto, May 1989, 103-113
• [Eng 91 ]Engelfriet, J., Branching Processes of Petri Nets, Acta Informatica 28 (1991) 575-591
• [EPS 73] Ehrig, H., Pfender, H., Schneider, H. J., Graph Grammars: An Algebraic Approach, Proc. of the IEEE Conf. on Automata and Switching Theory, Iowa City (1973) 167¬180
• [Espa 93] Esparza, J., Model Checking Using Net Unfoldings, in Proc. of TAPSOFT’93, Springer LNCS 668 (1993) 613-628
• [GM 89] Gurevich, Y., Moss, L. S., Algebraic Operational Semantics and Occam, in the Proceedings of CSL’89, Kaiserslautern, October 1989, Springer LNCS 440 (1989) 176-192
• [GoKa 91] Godefroid, P., Kabanza, F., An Efficient Reactive Planner for Synthesizing Reactive Plans, in Proc. of AAAI’91 (1991) 640-645
• [Ivowa 76] Kowalski, R., Logic for Problem Solving, North Holland, New York (1979)
• [MaWi 82] Maggiolo-Schettini, A., Winkowski, J., Processes of Transforming Structures, J. Comput. System Sei., Vol.24, No.3 (1982) 245-282
• [McM 93] McMillan, K., L., Using unfoldings to avoid the state explosion problem in the verification of asynchronous circuits, in Proc. of the 4th Workshop on Computer Aided Verification, Montreal 1992, G. v. Bochmann and D. K. Probst (Eds.), Springer LNCS 663 (1993) 164-174
• [MR 95] Montanari, U., Rossi, F., Contextual Nets, Acta Informatica 32 (1995) 545-596
• [VSY 98] Vogler, W., Semenov, A., Yakovlev, A., Unfolding and Finite Prefix for Nets with Read Arcs, Proc. of CONCUR’98, Nice, September 1998, Davide Sangiorgi and Robert de Simone (Eds.), Springer LNCS 1466 (1998) 501-516
• [Wink 01] Winkowski, J., A model of evolving relational structures and its application to plan-formation, ICS PAS Report 929 (2001)
• [Wink 02] Winkowski, J., Reachability in contextual nets, Fundamenta Informaticae 51 (2002) 235-250