No description available.

In this thesis we focus on the design and implementation of a particular framework of Possibilistic Defeasible Logic Programming (RP-DeLP). This framework is based on a general notion of collective (non-binary) conflict among arguments allowing to ensure direct and indirect consistency properties with respect to the strict knowledge. An output of an RP-DeLP program is a pair of sets of warranted and blocked conclusions (literals), all of them recursively based on warranted conclusions but, while warranted conclusions do not generate any conflict, blocked conclusions do. An RP-DeLP program may have multiple outputs in case of circular definitions of conflicts among arguments. We introduce two semantics, the first one where all possible outputs are computed and the second one which is a characterization of an unique output property. The computation of the outputs for both semantics relies on two main problems: the problem of finding a collective conflict among a set of arguments and the problem of finding almost valid arguments for a conclusion. Both problems are combinatorial problems, so we propose two resolution approaches: a first one based on SAT techniques and a second one based on Answer Set Programming techniques. We propose an implementation and we empirically test our algorithms. We provide an analysis on the performance of the implementation of the algorithms, and we explain the results on the resolution of some randomly generated problems. In this thesis we also focus on the resolution of some combinatorial problems. We analyze, design and implement some resolution tools for arithmetic problems, modular constraints and networking problems. We studied empirically how our approaches perform and we compared them to other solving techniques known as best proposals in the literature. / Esta tesis se centra en el diseño e implementación de un framework particular para Possibilistic Defeasible Logic Programming (RP-DeLP). Este framework está basado en la noción general de conflicto colectivo entre argumentos (no binario) que permite asegurar las propiedades de consistencia directa e indirecta respecto al conocimiento estricto. Una salida de un programa RP-DeLP es una tupla de conjuntos de conclusiones (literales) garantizadas y bloqueadas, todas ellas basadas recursivamente sobre conclusiones garantizadas con la particularidad de que mientras las conclusiones garantizadas no generan ningún conflicto, las conclusiones bloqueadas sí lo hacen. Un programa RP-DeLP puede tener múltiples salidas en el caso de que existan definiciones circulares de conflictos entre los argumentos. Se introducen dos semánticas, la primera donde se computan todas las posibles salidas del programa y una segunda que nace de la caracterización de la propiedad de la salida única. El cómputo de las salidas para ambas semánticas se basa en la solución de dos problemas principales: el problema de la búsqueda de argumentos almost valid para una conclusión y la búsqueda de conflictos colectivos entre un conjunto de argumentos. Ambos problemas son problemas combinatorios y se proponen dos aproximaciones de resolución diferentes: una primera aproximación basada en técnicas SAT y otra segunda aproximación basada en técnicas de Answer Set Programming. Se propone una implementación y también se prueba empíricamente el comportamiento de los algoritmos propuestos. A través de un análisis sobre el comportamiento de la implementación se explican los resultados obtenidos. Para ello se generan problemas aleatorios donde algunas propiedades pueden ser controladas mediante la configuración de parámetros de entrada. Adicionalmente esta tesis también se centra en la resolución de otros problemas combinatorios. Se analizan e implementan herramientas para la resolución de problemas aritméticos, restricciones modulares y problemas de redes de comunicaciones. Se propone un estudio empírico de las propuestas y se comparan con las aproximaciones, conocidas como más eficientes hasta el momento, de la literatura. / Aquesta tesi doctoral se centra en el disseny i implementació d'un framework particular per Possibilistic Defeasible Logic Programming (RP-DeLP). Aquest framework es basa en una noció de conflicte col·lectiu (no binària) entre arguments que permet assegurar les propietats de consistència directa i indirecta respecte del coneixement estricte. Una sortida d'un programa RP-DeLP és una parella de conjunts de conclusions garantides i bloquejades (literals), totes elles basades recursivament en conclusions prèviament garantides. La diferència radica en què mentre les conclusions garantides no generen cap conflicte, les conclusions bloquejades sí que ho fan. Un programa RP-DeLP pot tenir múltiples sortides en el cas de definicions circulars de conflictes entre arguments. S'introdueixen dues semàntiques pel sistema d'argumentació presentat. La primera d'elles pren en consideració totes les possibles sortides que poden ser obtingudes d'un programa RP-DeLP tenint en compte les diferents maneres de resoldre els conflictes circulars que poden sorgir. La segona semàntica se centra en el còmput d'una única sortida que està basada en la caracterització del que anomenem maximal ideal output. Aquesta sortida conté un nombre maximal de literals garantits, però que inclou només literals els arguments dels quals tenen els seus suports inclosos en la sortida. El comput de les sortides per ambdues semàntiques es basa en la resolució de dos problemes principals: el problema de trobar conflictes col·lectius entre un conjunt d'arguments i el problema de trobar arguments almost valid per una conclusió. Ambdós problemes són considerats problemes combinatoris i es proposen dues aproximacions per a la resolució: una primera aproximació basada en tècniques SAT i una segona basada en Answer Set Programming. Es proposa una implementació i una anàlisi empírica dels algorismes implementats. Aquests algorismes es proven sobre un conjunt de problemes generats aleatòriament mitjançant un generador que permet la configuració dels diferents paràmetres dels problemes generats. Un cop obtinguts els resultats, s'estudia quina afectació han tingut els diferents paràmetres observant el temps de resolució i la informació obtinguda. En aquesta tesi també s'estudien diferents tècniques de resolució per a altres problemes combinatoris. S'analitzen, dissenyen i implementen algunes eines de resolució per a problemes aritmètics, restriccions modulars i problemes de xarxes de comunicacions. S'ha estudiat com les aproximacions proposades es comporten en comparació amb altres tècniques proposades a la literatura considerades com les més eficients fins al moment.

No description available.

La majoria de metaheuristiques tenen una component aleatori, que normalment està basada en aleatorització uniforme -i.e., l'ús de la distribució de probabilitat uniforme per fer seleccions aleatòries. Per altra banda, el marc Multi-start biased Randomization of classical Heuristics with Adaptive local search proposa l'ús de aleatorització esbiaixada (no uniforme) per al disseny de algoritmes metaheuristics alternatius -i.e., l'ús de distribucions de probabilitat esbiaixades com la geomètrica o la triangular. En algunes situacions, aquesta aleatorització no uniforme ha obtingut una convergència més ràpida a la solució quasi òptima. El marc MIRHA també inclou un pas de cerca local per a millorar les solucions generades durant el procés iteratiu. A més, permet afegir passos de cerca adaptats al problema, com cache (memòria) o splitting (dividir i conquerir), que permeten la generació de solucions competitives (quasi òptimes). Els algoritmes dissenyats amb el marc MIRHA permeten obtenir solucions d'alta qualitat a problemes realistes en temps de computació raonables. A més, tendeixen a utilitzar un nombre reduït de paràmetres, el que els fa simples d'implementar i configurar en la majoria d'aplicacions pràctiques. El marc s'ha aplicat exitosament a diversos problemes d'enrutament i planificació. Un dels principals objectius d'aquesta tesi és desenvolupar nous algoritmes , basats en el marc mencionat, per solucionar problemes d'optimització combinatòria que poden ser d'interès a la industria de les telecomunicacions. / La mayoría de metaheurísticas tienen un componente aleatorio, que normalmente está basada en aleatorización uniforme -ie, el uso de la distribución de probabilidad uniforme para hacer selecciones aleatorias. Por otra parte, el marco Multi-start Biased Randomization of classical heurística with Adaptive local search propone el uso de aleatorización sesgada (no uniforme) para el diseño de algoritmos metaheurísticos alternativos -ie, el uso de distribuciones de probabilidad sesgadas como la geométrica o triangular. En algunas situaciones, esta aleatorización no uniforme ha obtenido una convergencia más rápida en la solución casi óptima. El marco MIRHA también incluye un paso de búsqueda local para mejorar las soluciones generadas durante el proceso iterativo. Además, permite añadir pasos de búsqueda adaptados al problema, como caché (memoria) o splitting (dividir y conquistar), que permiten la generación de soluciones competitivas (casi óptimas). Los algoritmos diseñados con el marco MIRHA permiten obtener soluciones de alta calidad a problemas realistas en tiempo de computación razonables. Además, tienden a utilizar un número reducido de parámetros, lo que los hace simples de implementar y configurar en la mayoría de aplicaciones prácticas. El marco se ha aplicado exitosamente a varios problemas de enrutamiento y planificación. Uno de los principales objetivos de esta tesis es desarrollar nuevos algoritmos, basados ¿¿en el marco mencionado, para solucionar problemas de optimización combinatoria que pueden ser de interés en la industria de las telecomunicaciones. / Most metaheuristics contain a randomness component, which is usually based on uniform randomization -i.e., the use of the Uniform probability distribution to make random choices. However, the Multi-start biased Randomization of classical Heuristics with Adaptive local search framework proposes the use of biased (non-uniform) randomization for the design of alternative metaheuristics -i.e., the use of skewed probability distributions such as the Geometric or Triangular ones. In some scenarios, this non-biased randomization has shown to provide faster convergence to near-optimal solutions. The MIRHA framework also includes a local search step for improving the incumbent solutions generated during the multi-start process. It also allows the addition of tailored local search components, like cache (memory) or splitting (divide-and-conquer) techniques, that allow the generation of competitive (near-optimal) solutions. The algorithms designed using the MIRHA framework allows to obtain "high-quality" solutions to realistic problems in reasonable computing times. Moreover, they tend to use a reduced number of parameters, which makes them simple to implement and configure in most practical applications. This framework has successfully been applied in many routing and scheduling problems. One of the main goals of this thesis is to develop new algorithms, based in the aforementioned framework, for solving some combinatorial optimization problems that can be of interest in the telecommunication industry.

This thesis focuses on the development of a distributed mobile robot localization and communication system for special interventions like those carried out by fire-fighters in fire ground search and rescue. The use case scenario is related to the one described for the GUARDIANS EU project, where a swarm formation of mobile robots accompany a fire fighter during a rescue intervention in a warehouse. In this line, localizing the robots and the fire fighter during an indoor intervention with the presence of smoke is one of the more interesting challenges in this scenario. Several localization techniques have been developed using ultrasonic sensors, radio frequency signals and visual information. It has also been studied several communication protocols that can help to improve the efficiency of the system in such scenario and a proposal for designing a cross-layer communication platform that improves the connectivity of the mobile nodes during an intervention and reduces the number of lost data packets.