Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > publis

PhD thesis

Evacuation Planning using Answer Set Programming
12/2005
Établissement : INSA Lyon et Universidad de las Américas-Puebla
Jury
Contact : inconnu

TEL : hal-01469315

Abstract

Currently, people involved in protection against disaster situations must make the de- cisions about preparing and executing evacuation plans for potential causes of disaster. Hence, it would be desirable to develop a system capable of obtaining and analyz- ing evacuation plans based on knowledge about their particular environment, the ge- ographic data and their own capabilities, and of exchanging information and services with similar systems as well as with humans. A possible formalism used for develop such system could be Answer Set Programming (ASP). ASP is a declarative knowledge representation and logic programming language[13]. 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 defining evacuation plans. The motivation of our work is based on the idea that ASP presents 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 understand. There exists Answer Set Planning that provides a natural and elegant way to model planning problems [15]. ASP uses the concept of negation as failure that allows us to express exceptions and represent incomplete knowledge. In ASP there exist different 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-defined evacuation routes. However, in a real case is possible that part of the pre-defined evacuation routes become blocked. In this case, definition 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 different levels over the alternative plans. We also define PP par language, as an extension of PP language where its connectives allow us 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 (LT L), since we consider that language PP could take advantage of the working framework of LT L 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 different answer set semantics of a program. One of them is a new semantics introduced in this work, called partial answer sets.

Additional information

Thèse en cotutelle avec le Mexique

BibTex

Download

@PhDThesis{Liris-4148,
  title         = {{Evacuation Planning using Answer Set Programming}},
  author        = {Claudia {Zepeda-Cortes}},
  year          = {2005},
  month         = dec,
  school        = {INSA Lyon et Universidad de las Américas-Puebla},
  type          = {Thèse de Doctorat en Informatique},
   language      = {fr},
  url           = {http://liris.cnrs.fr/publis/?id=4148},
  note          = {Thèse en cotutelle avec le Mexique}
}