Tesi di Dottorato

Permanent URI for this communityTesi di Dottorato

Browse

Has files: YesSubject: search.filters.subject.Algoritmi

Search Results

Now showing 1 - 10 of 18
  • No Thumbnail Available
    Item
    Simulation-based optimization in port logistics
    (2017) Mazza, Rina Mary; Grandinetti, Lucio; Legato, Pasquale
  • No Thumbnail Available
    Item
    Computational tasks in answer set programming: algorithms and implementation
    (2014-12-01) Dodaro, Carmine; Leone, Nicola; Ricca, Francesco
    L’Answer Set Programming (ASP) è un paradigma di programmazione dichiarativa basato sulla semantica dei modelli stabili. L’idea alla base di ASP è di codificare un problema computazionale in un programma logico i cui modelli stabili, anche detti answer set, corrispondono alle soluzioni del problema. L’espressività di ASP ed il numero crescente delle sue applicazioni hanno reso lo sviluppo di nuovi sistemi ASP un tema di ricerca attuale ed importante. La realizzazione di un sistema ASP richiede di implementare soluzioni efficienti per vari task computazionali. Questa tesi si occupa delle problematiche relative alla valutazione di programmi proposizionali, ed in particolare affronta i task di model generation, answer set checking, optimum answer set search e cautious reasoning. La combinazione dei primi due task corrisponde alla computazione degli answer set. Infatti, il task di model generation consiste nel generare dei modelli del programma in input, mentre il task di answer set checking ha il compito di verificare che siano effettivamente modelli stabili. Il primo task è correlato alla risoluzione di formule SAT, ed è implementato -nelle soluzioni moderne- con un algoritmo di backtracking simile al Conflict-Driven Clause Learning (CDCL); il secondo è risolto applicando una riduzione al problema dell’insoddisfacibilità di una formula SAT. In presenza di costrutti di ottimizzazione l’obiettivo di un sistema ASP è l’optimum answer set search, che corrisponde a calcolare un answer set che minimizza il numero di violazioni dei cosiddetti weak constraint presenti nel programma. Il cautious reasoning è il task principale nelle applicazioni dataoriented di ASP, e corrisponde a calcolare un sottoinsieme degli atomi che appartengono a tutti gli answer set di un programma. Si noti che tutti questi task presentano una elevata complessità computazionale. I contributi di questa tesi sono riassunti di seguito: (I) è stato studiato il task di model generation ed è stata proposta per la sua risoluzione una combinazione di tecniche che sono state originariamente utilizzate per risolvere il problema SAT; (II) è stato proposto un nuovo algoritmo per l’answer set checking che minimizza l’overhead dovuto all’esecuzione di chiamate multiple ad un oracolo co-NP. Tale algoritmo si basa su una strategia di valutazione incrementale ed euristiche progettate specificamente per migliorare l’efficienza della risoluzione di tale problema; (III) è stata proposta una famiglia di algoritmi per il calcolo di answer set ottimi di programmi con weak constraint. Tali soluzioni sono state ottenute adattando algoritmi proposti per risolvere il problema MaxSAT; (IV) è stato introdotto un nuovo framework di algoritmi anytime per il cautious reasoning in ASP che estende le proposte esistenti ed include un nuovo algoritmo ispirato a tecniche per il calcolo di backbone di teorie proposizionali. Queste tecniche sono state implementate in wasp 2, un nuovo sistema ASP per programmi proposizionali. L’efficacia delle tecniche proposte e l’efficienza del nuovo sistema sono state valutate empiricamente su istanze utilizzate nella competizioni per sistemi ASP e messe a disposizione sul Web.
  • No Thumbnail Available
    Item
    Design and performance evaluation of algorithms for wireless self-organizing systems
    (2014-11-28) Surace, Rosario; Greco, Sergio; Loscrì, Valeria; Aloi, Gianluca
    The work done during the PhD course involves the study of the Self- Organization of wireless sensors, robots and UAV networks. In particular, this thesis investigates how each node composing the system can take advantage from the Self-Organization and from mobility, in a way to optimize some networks parameters as coverage and energy consumption. Self-Organization is a process in which pattern at the global level of a system emerges solely from numerous interactions among the lower-level components of a system. The rules specifying interactions among the systems components are executed using only local information, without reference to the global pattern [1]. Mobility, although still for some types of systems is not considered a primitive of the network: in recent years has been the subject of many studies just as useful feature to achieve certain objectives, not least the energy consumption in transmission. The network issues has been addressed using different approaches from the theoretical studies aimed at finding the maximum achievable performance benchmarks, through the introduction of appropriate optimization models, the proposal of distributed heuristics and more realistic communication protocols, and the use of biology-inspired mechanisms, such as genetic algorithms (GA) and neural networks (NN). The purpose of this type of approach is to move in the direction of networks that are able to self-organize by adapting to different environmental conditions and dynamic as well as hard scenarios (i.e. environment disasters). The rest of the thesis is organized as follows: in Chapter 1 background on Self-Organizing Systems is given. In Chapter 2 we investigate on the impact of the Propagation Environment on Controlled Mobility Algorithms; distributed heuristics to Film Sport Events with Flying Robots in Chapter 3 and Bio- Inspired approaches in Chapter 4. Finally, a new communications protocol for WSN called Decentralized Time-Synchronized Channel Swapping is analyzed in Chapter 5.
  • No Thumbnail Available
    Item
    Metodi di fusione dei dati per sistemi di assistenza alla guida
    (2012-10-24) Lupia, Marco; Palopoli, Luigi; Casavola, Alessandro
    Questo documento riporta tutta l'attivit a svolta durante il corso di dottora- to riguardo lo studio, l'applicazione e la sperimentazione di metodi di Data Fusion nell'ambito dei sistemi avanzati di assistenza alla guida per il miglio- ramento delle prestazioni e dell'a dabilit a. In linea di principio, sembra ra- gionevole a ermare che combinando in modo ottimale le informazioni proveni- enti da pi u sensori e possibile progettare e realizzare un sistema meno sensibile alle variazioni ambientali e a possibili errori di misura dovuti alla presenza di outliers. Tuttavia, dal punto di vista pratico i costi aggiuntivi che si devono sostenere, sia in termini di hardware necessario alla raccolta dei dati dai sen- sori addizionali che per la necessit a di disporre di sistemi di calcolo pi u potenti, potrebbero non essere giusti cati se i miglioramenti ottenuti nelle situazioni pi u probabili e pi u realistiche di utilizzo sono modesti. Il presente documento o re, innanzitutto, una panoramica su vari algoritmi di visione arti ciale utilizzati per il riconoscimento della segnaletica orizzon- tale e per la stima del tempo di invasione (tTLC). Quest'ultimo parametro gioca un ruolo determinante nell'avvertimento tempestivo del conducente in caso di superamento dei limiti della carreggiata. I vari algoritmi sono stati testati in varie condizioni di guida, valutandone le prestazioni conseguibili e il carico computazionale richiesto. Segue un'analisi dello stato dell'arte dei metodi e delle tecniche di Data Fu- sion pi u promettenti e che che meglio si prestano a migliorare l'accuratezza del calcolo della stima del tempo di invasione ttlc grazie alla disponibilit a di altri sensori oltre alla telecamera. Speci catamente, si sono confrontati i vari meto- di e algoritmi di Data Fusion, particolarizzati rispetto a vari modelli matem- atici della vettura e ai sensori disponibili, valutando le loro prestazioni in situ- azioni tipiche di guida e soprattutto rispetto all'errore percentuale di stima del tempo di invasione ttlc ottenuto, valutando anche il carico computazionale corrispondente. Gli algoritmi pi u promettenti sono stati implementati su piattaforma embedded.Questo documento riporta tutta l'attivit a svolta durante il corso di dottora- to riguardo lo studio, l'applicazione e la sperimentazione di metodi di Data Fusion nell'ambito dei sistemi avanzati di assistenza alla guida per il miglio- ramento delle prestazioni e dell'a dabilit a. In linea di principio, sembra ra- gionevole a ermare che combinando in modo ottimale le informazioni proveni- enti da pi u sensori e possibile progettare e realizzare un sistema meno sensibile alle variazioni ambientali e a possibili errori di misura dovuti alla presenza di outliers. Tuttavia, dal punto di vista pratico i costi aggiuntivi che si devono sostenere, sia in termini di hardware necessario alla raccolta dei dati dai sen- sori addizionali che per la necessit a di disporre di sistemi di calcolo pi u potenti, potrebbero non essere giusti cati se i miglioramenti ottenuti nelle situazioni pi u probabili e pi u realistiche di utilizzo sono modesti. Il presente documento o re, innanzitutto, una panoramica su vari algoritmi di visione arti ciale utilizzati per il riconoscimento della segnaletica orizzon- tale e per la stima del tempo di invasione (tTLC). Quest'ultimo parametro gioca un ruolo determinante nell'avvertimento tempestivo del conducente in caso di superamento dei limiti della carreggiata. I vari algoritmi sono stati testati in varie condizioni di guida, valutandone le prestazioni conseguibili e il carico computazionale richiesto. Segue un'analisi dello stato dell'arte dei metodi e delle tecniche di Data Fu- sion pi u promettenti e che che meglio si prestano a migliorare l'accuratezza del calcolo della stima del tempo di invasione ttlc grazie alla disponibilit a di altri sensori oltre alla telecamera. Speci catamente, si sono confrontati i vari meto- di e algoritmi di Data Fusion, particolarizzati rispetto a vari modelli matem- atici della vettura e ai sensori disponibili, valutando le loro prestazioni in situ- azioni tipiche di guida e soprattutto rispetto all'errore percentuale di stima del tempo di invasione ttlc ottenuto, valutando anche il carico computazionale corrispondente. Gli algoritmi pi u promettenti sono stati implementati su piattaforma embedded.
  • No Thumbnail Available
    Item
    Metodi e algoritmi per il riconoscimento del livello di distrazione e affaticamento nella guida di autoveicoli
    (2012-10-24) Cario, Gianni; Palopoli, Luigi; Casavola, Alessandro
  • No Thumbnail Available
    Item
  • No Thumbnail Available
    Item
    Distributed command governor strategies for multi-agent dynamical systems
    (2011-11-23) Francesco Tedesco, Francesco Tedesco; Palopoli, Luigi; Casavola, Alessandro
    This dissertation presents a class of novel distributed supervision strategies for multi-agent linear systems connected via data networks and subject to coordination constraints. Such a coordination-by-constraint paradigm is characterized by a set of spatially distributed dynamic systems, connected via communication channels, with possibly dynamical coupling amongst them which need to be supervised and coordinated in order to accomplish their overall objective. The basic design philosophy of the Command Governor (CG) set-point management is used here in order to maintain a pre-stabilized system within prescribed constraints. While in traditional CG schemes the set-point manipulation is undertaken on the basis of the actual measure of the state, in this dissertation it is shown that the CG design problem can be solved also in the case that such an explicit measure is not available by forcing the state evolutions to stay ”not too far” from the manifold of feasible steady-states. This approach, referred to as Feed-Forward CG (FF-CG), is a convenient solution to be used in distributed applications where the cost of measuring the overall state and distributing it amongst the agents may be a severe limitation. Several distributed strategies, based both on CG and FF-CG ideas, will be fully described and analyzed. First, we propose some “non-iterative” schemes in which the agents acting as supervisors communicate once during the decision process. In this respect, a “sequential” distributed strategy in which only one agent at the time is allowed to manipulate its own reference signal is proposed. Such a strategy, although interesting by itself in some applications, will be instrumental to introduce a more effective “parallel” distributed strategy, in which all agents are allowed, under certain conditions, to modify their own reference signals simultaneously. Then an “iterative” procedure, borrowed from the literature, has been here adapted in order to build more efficient distributed schemes which however require larger amount of data exchanges for their implementation. With the aim of evaluating the distributed methods here proposed, several cases of study involving the coordination autonomous vehicles, power networks and water networks management are illustrated.
  • No Thumbnail Available
    Item
    On the problem of checking chase termination
    (2011-11-23) Spezzano, Francesca; Palopoli, Luigi; Greco, Sergio
  • No Thumbnail Available
    Item
    The Generative Aspects of Count Constraints: Complexity, Languages and Algorithms
    (2011-11-23) Serra, Edoardo; Palopoli, Luigi; Saccà, Domenico
  • No Thumbnail Available
    Item
    Mobile robots:localization and mapping alogorithms
    (2013-11-27) D'Alfonso, Luigi; Greco, Sergio; Muraca, Pietro; Garone, Emanuele
    In recent years, mobile robots start to be very often used in various applications involving home automation, planetary exploration, regions surveillance, rescue missions, ruins exploration. In all these elds, to accomplish its tasks, a mobile robot needs to navigate into an environment facing the localization, mapping and path planning problems. In this thesis a set of new algorithms to solve the mobile robots localization and mapping problems are proposed. The aim is to provide an accurate mobile robot estimated pose and to build a reliable map for the environment where the robot moves, ensuring algorithms computational costs low enough so that the algorithms can be used in real time, while the robot is moving. The localization problem is faced in static and dynamic contexts, assuming the environment surrounding the robot completely known, partially known or totally unknown. In the static context, localization algorithms based on the use of cameras and inertial measurement units are proposed. In the dynamic context, the mobile robots localization problem is solved by developing a set of new Kalman lter versions. About the mapping problem, two novel mapping models are de- ned. These models are used along with the proposed localization techniques to develop three algorithms able to solve the Simultaneous Localization and Mapping (SLAM) problem. All the proposed solutions are tested through numerical simulations and experimental tests in a real environment and using a real mobile robot. The results show the e ectiveness of the proposed algorithms, encouraging further researches.