1. Inicio
  2. Atrás
Título: Evacuation Planning using Answer Set Programming
Autores: Zepeda Cortés, Claudia
Fecha: 2005-12-12
Publicador: CIRIA
Fuente:
Tipo: Electronic Thesis or Dissertation
Tesis
Tema: Ciencias de la Computación
Descripción: Currently, people involved in protection against disaster situations must make the decisions about preparing and executing evacuation plans for potential causes of disaster. Hence, it would be desirable to develop a system capable of obtaining and analyzing evacuation plans based on knowledge about their particular environment, the geographic data and their own capabilities, and of exchanging information and services with similar systems as well as with persons. A possible formalism used to develop such system could be Answer Set Programming (ASP). ASP is a declarative knowledge representation and logic programming language[14]. ASP represents a new paradigm for logic programming that allows, using the concept of negation as failure, to handle problems with default knowledge and produce non-monotonic reasoning. Specifically, the objective of our work is to investigate and evaluate the capabilities of Answer Set Programming to represent disaster situations in order to give support in de¯ning evacuation plans. The motivation of our work is based on the idea that ASP posses most of the capabilities that would be desirable that such system should have: It is possible translate geographic information into a format that ASP can handle. There exists Answer Set Planning that provides a natural and elegant way to model planning problems [16]. ASP uses the concept of negation as failure that allows us to express exceptions and represent incomplete knowledge. In ASP there exist di®erent approaches to express preferences. ASP allows to express restrictions. In order to investigate and evaluate the capabilities of ASP to represent disaster situations we studied the format of geographic information. Based in our own experience we introduce a procedure to construct the hazard zone background knowledge from non spatial part of the geographic information. Normally, in a zone in risk there is a set of pre-de¯ned evacuation routes. However, in a real case it is possible that part of the pre-de¯ned evacuation routes become blocked. In this case de¯nition of alternative evacuation plans are needed. We use Consistency Restoring rules (CR-rules) in order to obtain the alternative evacuation plans. We also prove that programs with CR-rules can be properly represented using ordered disjunction logic programs (ODLP). The alternative evacuation routes obtained using CR-rules do not consider any other characteristic of the path that they follow. Hence, we propose to use language PP in order to express preferences at di®erent levels over the alternative plans. We also de¯ne PPpar language, as an extension of PP language where the connectives allow to represent compactly preferences having a particular property. Additionally, we present a brief overview about the relationship between language PP and propositional Linear Temporal Logic (LTL), since we consider that language PP could take advantage of the working framework of LTL to express preferences. We also propose an extension of ODLP to a wider class of logic programs. Moreover, we show that in particular extended ordered rules with negated negative literals could be useful to allow a simpler and easier encoding of obtaining the preferred plans w.r.t preferences expressed in PP. Finally, we introduce the notion of Semantic Contents of a program as an alternative point of view to obtain di®erent answer set semantics of a program. One of them is a new semantics introduced in this work, called partial answer sets.
Idioma: Otro