Speeding-up state-space search by automatic abstraction.

FieldValue
dc.contributor.advisorHolte, Robert,
dc.contributor.authorMkadmi, Taieb.
dc.date.accessioned2009-03-23T14:16:03Z
dc.date.available2009-03-23T14:16:03Z
dc.date.created1993
dc.date.issued1993
dc.identifier.citationSource: Masters Abstracts International, Volume: 32-03, page: 0993.
dc.identifier.isbn9780315838307
dc.identifier.urihttp://hdl.handle.net/10393/6908
dc.identifier.urihttp://dx.doi.org/10.20381/ruor-11518
dc.description.abstractMost existing abstraction algorithms are sensitive to the initial problem formulation. Given two different descriptions of the same space, they will produce different abstractions, of which one might be efficient for problem-solving while the other might be inefficient. This thesis presents a completely automated approach to generating and using abstractions for problem solving in state-spaces. The strategy to overcome the problem of sensitivity is called the graph relabelling strategy. The abstraction algorithms used are all based on that strategy and on a theoretical study of the complexity to abstract and to search using an abstraction. This study presents theorems and compares analytical results to some known graph algorithms. Extensive experiments confirm that our abstractions can be quickly computed and greatly reduce problem-solving time in state-spaces, especially those with invertible operators.
dc.format.extent159 p.
dc.publisherUniversity of Ottawa (Canada)
dc.subject.classificationComputer Science.
dc.titleSpeeding-up state-space search by automatic abstraction.
dc.typeThesis
dc.degree.nameM.C.Sc.
dc.degree.levelMasters
CollectionTh├Ęses, 1910 - 2010 // Theses, 1910 - 2010

Files
MM83830.PDF2.98 MBAdobe PDFOpen