# All Publications

 Hide abstracts BibTeX entries 2015 [199] Mikael Nilsson, Jonas Kvarnström and Patrick Doherty. 2015. Revisiting Classical Dynamic Controllability: A Tighter Complexity Analysis. Lecture Notes in Artificial Intelligence, 8946(??):243–261. Springer International Publishing. DOI: 10.1007/978-3-319-25210-0. Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are uncontrollable (determined by nature), as is often the case for actions in planning. It is essential to verify that such networks are dynamically controllable (DC) -- executable regardless of the outcomes of uncontrollable durations -- and to convert them to an executable form. We use insights from incremental DC verification algorithms to re-analyze the original, classical, verification algorithm. This algorithm is the entry level algorithm for DC verification, based on a less complex and more intuitive theory than subsequent algorithms. We show that with a small modification the algorithm is transformed from pseudo-polynomial to O(n4) which makes it still useful. We also discuss a change reducing the amount of work performed by the algorithm. [198] Martin Danelljan, Fahad Shahbaz Khan, Michael Felsberg, Karl Granström, Fredrik Heintz, Piotr Rudol, Mariusz Wzorek, Jonas Kvarnström and Patrick Doherty. 2015. A Low-Level Active Vision Framework for Collaborative Unmanned Aircraft Systems. In Lourdes Agapito, Michael M. Bronstein and Carsten Rother, editors, Computer Vision - ECCV 2014 Workshops, Zurich, Switzerland, September 6-7 and 12, pages 223–237. In series: Lecture Notes in Computer Science #8925. Springer Publishing Company. ISBN: 978-3-319-16177-8 (print), 978-3-319-16178-5 (online). DOI: 10.1007/978-3-319-16178-5_15. Micro unmanned aerial vehicles are becoming increasingly interesting for aiding and collaborating with human agents in myriads of applications, but in particular they are useful for monitoring inaccessible or dangerous areas. In order to interact with and monitor humans, these systems need robust and real-time computer vision subsystems that allow to detect and follow persons.In this work, we propose a low-level active vision framework to accomplish these challenging tasks. Based on the LinkQuad platform, we present a system study that implements the detection and tracking of people under fully autonomous flight conditions, keeping the vehicle within a certain distance of a person. The framework integrates state-of-the-art methods from visual detection and tracking, Bayesian filtering, and AI-based control. The results from our experiments clearly suggest that the proposed framework performs real-time detection and tracking of persons in complex scenarios [197] Patrick Doherty and Andrzej Szalas. 2015. Stability, Supportedness, Minimality and Kleene Answer Set Programs. In Thomas Eiter, Hannes Strass, Mirosław Truszczynski, Stefan Woltran, editors, Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation: Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday, pages 125–140. In series: Lecture Notes in Computer Science #9060. Springer. ISBN: 978-3-319-14725-3 (softcover), 978-3-319-14726-0 (eBook). DOI: 10.1007/978-3-319-14726-0_9. Link to full text: http://www.ida.liu.se/divisions/aiics/pu... Answer Set Programming is a widely known knowledge representation framework based on the logic programming paradigm that has been extensively studied in the past decades. The semantic framework for Answer Set Programs is based on the use of stable model semantics. There are two characteristics intrinsically associated with the construction of stable models for answer set programs. Any member of an answer set is supported through facts and chains of rules and those members are in the answer set only if generated minimally in such a manner. These two characteristics, supportedness and minimality, provide the essence of stable models. Additionally, answer sets are implicitly partial and that partiality provides epistemic overtones to the interpretation of disjunctiver ules and default negation. This paper is intended to shed light on these characteristics by defining a semantic framework for answer set programming based on an extended first-order Kleene logic with weak and strong negation. Additionally, a definition of strongly supported models is introduced, separate from the minimality assumption explicit in stable models. This is used to both clarify and generate alternative semantic interpretations for answer set programs with disjunctive rules in addition to answer set programs with constraint rules. An algorithm is provided for computing supported models and comparative complexity results between strongly supported and stable model generation are provided. [196] Olov Andersson, Fredrik Heintz and Patrick Doherty. 2015. Model-Based Reinforcement Learning in Continuous Environments Using Real-Time Constrained Optimization. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI), pages 2497–2503. AAAI Press. ISBN: 978-1-57735-698-1. Reinforcement learning for robot control tasks in continuous environments is a challenging problem due to the dimensionality of the state and action spaces, time and resource costs for learning with a real robot as well as constraints imposed for its safe operation. In this paper we propose a model-based reinforcement learning approach for continuous environments with constraints. The approach combines model-based reinforcement learning with recent advances in approximate optimal control. This results in a bounded-rationality agent that makes decisions in real-time by efficiently solving a sequence of constrained optimization problems on learned sparse Gaussian process models. Such a combination has several advantages. No high-dimensional policy needs to be computed or stored while the learning problem often reduces to a set of lower-dimensional models of the dynamics. In addition, hard constraints can easily be included and objectives can also be changed in real-time to allow for multiple or dynamic tasks. The efficacy of the approach is demonstrated on both an extended cart pole domain and a challenging quadcopter navigation task using real data. 2014 [195] Patrick Doherty, Jonas Kvarnström, Mariusz Wzorek, Piotr Rudol, Fredrik Heintz and Gianpaolo Conte. 2014. HDRC3 - A Distributed Hybrid Deliberative/Reactive Architecture for Unmanned Aircraft Systems. In Kimon P. Valavanis, George J. Vachtsevanos, editors, Handbook of Unmanned Aerial Vehicles, pages 849–952. Springer Science+Business Media B.V.. ISBN: 978-90-481-9706-4, 978-90-481-9707-1. DOI: 10.1007/978-90-481-9707-1_118. Find book at a Swedish library/Hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/16541662 Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?qt=worldc... This chapter presents a distributed architecture for unmanned aircraft systems that provides full integration of both low autonomy and high autonomy. The architecture has been instantiated and used in a rotorbased aerial vehicle, but is not limited to use in particular aircraft systems. Various generic functionalities essential to the integration of both low autonomy and high autonomy in a single system are isolated and described. The architecture has also been extended for use with multi-platform systems. The chapter covers the full spectrum of functionalities required for operation in missions requiring high autonomy. A control kernel is presented with diverse flight modes integrated with a navigation subsystem. Specific interfaces and languages are introduced which provide seamless transition between deliberative and reactive capability and reactive and control capability. Hierarchical Concurrent State Machines are introduced as a real-time mechanism for specifying and executing low-level reactive control. Task Specification Trees are introduced as both a declarative and procedural mechanism for specification of high-level tasks. Task planners and motion planners are described which are tightly integrated into the architecture. Generic middleware capability for specifying data and knowledge flow within the architecture based on a stream abstraction is also described. The use of temporal logic is prevalent and is used both as a specification language and as an integral part of an execution monitoring mechanism. Emphasis is placed on the robust integration and interaction between these diverse functionalities using a principled architectural framework. The architecture has been empirically tested in several complex missions, some of which are described in the chapter. [194] Oleg Burdakov, Patrick Doherty and Jonas Kvarnström. 2014. Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance. In Butenko, S., Pasiliao, E.L., Shylo, V., editors, Examining Robustness and Vulnerability of Networked Systems, pages 26–50. In series: NATO Science for Peace and Security Series - D: Information and Communication Security #Volume 37. IOS Press. ISBN: 978-1-61499-390-2 (print), 978-1-61499-391-9 (online). DOI: 10.3233/978-1-61499-391-9-26. Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=978-1-6... We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances.For the hop-constrained DSTP, we propose local search strategies aimed at improving any heuristically produced initial Steiner tree. They are based on solving a sequence of hop-constrained shortest path problems for which we have recently developed efficient label correcting algorithms.The presented approach is applied to finding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The efficiency of our algorithms is illustrated by results of numerical experiments involving problem instances with up to 40 000 nodes and up to 20 million arcs. [193] Oleg Burdakov, Patrick Doherty and Jonas Kvarnström. 2014. Optimal Scheduling for Replacing Perimeter Guarding Unmanned Aerial Vehicles. Technical Report. In series: LiTH-MAT-R #2014:09. Linköping University Electronic Press. 13 pages. Guarding the perimeter of an area in order to detect potential intruders is an important task in a variety of security-related applications. This task can in many circumstances be performed by a set of camera-equipped unmanned aerial vehicles (UAVs). Such UAVs will occasionally require refueling or recharging, in which case they must temporarily be replaced by other UAVs in order to maintain complete surveillance of the perimeter. In this paper we consider the problem of scheduling such replacements. We present optimal replacement strategies and justify their optimality. [192] Oleg Burdakov, Patrick Doherty and Jonas Kvarnström. 2014. Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance. Technical Report. In series: LiTH-MAT-R #2014:10. Linköping University Electronic Press. 25 pages. We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances. For the hop-constrained DSTP, we propose local search strategies aimed at improving any heuristically produced initial Steiner tree. They are based on solving a sequence of hop-constrained shortest path problems for which we have recently developed ecient label correcting algorithms. The presented approach is applied to nding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The eciency of our algorithms is illustrated by results of numerical experiments involving problem instances with up to 40 000 nodes and up to 20 million arcs. [191] Gianpaolo Conte, Piotr Rudol and Patrick Doherty. 2014. Evaluation of a Light-weight Lidar and a Photogrammetric System for Unmanned Airborne Mapping Applications: [Bewertung eines Lidar-systems mit geringem Gewicht und eines photogrammetrischen Systems für Anwendungen auf einem UAV]. Photogrammetrie - Fernerkundung - Geoinformation, ??(4):287–298. E. Schweizerbart'sche Verlagsbuchhandlung. Link to article: http://www.ingentaconnect.com/content/sc... This paper presents a comparison of two light-weight and low-cost airborne mapping systems. One is based on a lidar technology and the other on a video camera. The airborne lidar system consists of a high-precision global navigation satellite system (GNSS) receiver, a microelectromechanical system (MEMS) inertial measurement unit, a magnetic compass and a low-cost lidar scanner. The vision system is based on a consumer grade video camera. A commercial photogrammetric software package is used to process the acquired images and generate a digital surface model. The two systems are described and compared in terms of hardware requirements and data processing. The systems are also tested and compared with respect to their application on board of an unmanned aerial vehicle (UAV). An evaluation of the accuracy of the two systems is presented. Additionally, the multi echo capability of the lidar sensor is evaluated in a test site covered with dense vegetation. The lidar and the camera systems were mounted and tested on-board an industrial unmanned helicopter with maximum take-off weight of around 100 kilograms. The presented results are based on real flight-test data. [190] Mikael Nilsson, Jonas Kvarnström and Patrick Doherty. 2014. Incremental Dynamic Controllability in Cubic Worst-Case Time. In Cesta, A; Combi, C; Laroussinie, F, editors, Proceedings of the 21st International Symposium on Temporal Representation and Reasoning (TIME), pages 17–26. In series: International Workshop on Temporal Representation and Reasoning. Proceedings #??. IEEE Computer Society Digital Library. ISBN: 978-1-4799-4227-5. DOI: 10.1109/TIME.2014.13. It is generally hard to predict the exact duration of an action. The uncertainty in the duration is often modeled in temporal planning by the use of upper bounds on durations, with the assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false: If we finish cooking too early, the dinner will be cold before everyone is ready to eat. Simple Temporal Problems with Uncertainty (STPUs) allow us to model such situations. An STPU-based planner must verify that the plans it generates are executable, captured by the property of dynamic controllability. The EfficientIDC (EIDC) algorithm can do this incrementally during planning, with an amortized complexity per step of $O(n^3)$ but a worst-case complexity per step of $O(n^4)$. In this paper we show that the worst-case run-time of EIDC does occur, leading to repeated reprocessing of nodes in the STPU while verifying the dynamic controllability property. We present a new version of the algorithm, called EIDC2, which through optimal ordering of nodes avoids any need for reprocessing. This gives EIDC2 a strictly lower worst-case run-time, making it the fastest known algorithm for incrementally verifying dynamic controllability of STPUs. [189] Mikael Nilsson, Jonas Kvarnström and Patrick Doherty. 2014. EfficientIDC: A Faster Incremental Dynamic Controllability Algorithm. In Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS), pages 199–207. ISBN: ISBN:978-1-57735-660-8. Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are uncontrollable (determined by nature), as is often the case for actions in planning. It is essential to verify that such networks are dynamically controllable (DC) – executable regardless of the outcomes of uncontrollable durations – and to convert them to an executable form. We use insights from incremental DC verification algorithms to re-analyze the original verification algorithm. This algorithm, thought to be pseudo-polynomial and subsumed by an O(n5) algorithm and later an O(n4) algorithm, is in fact O(n4) given a small modification. This makes the algorithm attractive once again, given its basis in a less complex and more intuitive theory. Finally, we discuss a change reducing the amount of work performed by the algorithm. [188] Mikael Nilsson, Jonas Kvarnström and Patrick Doherty. 2014. Classical Dynamic Controllability Revisited: A Tighter Bound on the Classical Algorithm. In Proceedings of the 6th International Conference on Agents and Artificial Intelligence (ICAART), pages 130–141. DOI: 10.5220/0004815801300141. Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems wheresome durations are uncontrollable (determined by nature), as is often the case for actions in planning. It is essentialto verify that such networks are dynamically controllable (DC) – executable regardless of the outcomesof uncontrollable durations – and to convert them to an executable form. We use insights from incrementalDC verification algorithms to re-analyze the original verification algorithm. This algorithm, thought to bepseudo-polynomial and subsumed by an O(n5) algorithm and later an O(n4) algorithm, is in fact O(n4) givena small modification. This makes the algorithm attractive once again, given its basis in a less complex andmore intuitive theory. Finally, we discuss a change reducing the amount of work performed by the algorithm. 2013 [187] Patrick Doherty, Fredrik Heintz and Jonas Kvarnström. 2013. Robotics, Temporal Logic and Stream Reasoning. In Proceedings of Logic for Programming Artificial Intelligence and Reasoning (LPAR), 2013. [186] Patrick Doherty and Andrzej Szalas. 2013. Automated Generation of Logical Constraints on Approximation Spaces Using Quantifier Elimination. Fundamenta Informaticae, 127(1-4):135–149. IOS Press. DOI: 10.3233/FI-2013-900. Note: Funding Agencies|Swedish Research Council (VR) Linnaeus Center CADICS||ELLIIT Excellence Center at Linkoping-Lund in Information Technology||CUAS project||SSF, the Swedish Foundation for Strategic Research|| This paper focuses on approximate reasoning based on the use of approximation spaces. Approximation spaces and the approximated relations induced by them are a generalization of the rough set-based approximations of Pawlak. Approximation spaces are used to define neighborhoods around individuals and rough inclusion functions. These in turn are used to define approximate sets and relations. In any of the approaches, one would like to embed such relations in an appropriate logical theory which can be used as a reasoning engine for specific applications with specific constraints. We propose a framework which permits a formal study of the relationship between properties of approximations and properties of approximation spaces. Using ideas from correspondence theory, we develop an analogous framework for approximation spaces. We also show that this framework can be strongly supported by automated techniques for quantifier elimination. [185] Gianpaolo Conte, Alexander Kleiner, Piotr Rudol, Karol Korwel, Mariusz Wzorek and Patrick Doherty. 2013. Performance evaluation of a light weight multi-echo LIDAR for unmanned rotorcraft applications. In International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XL-1/W2. The paper presents a light-weight and low-cost airborne terrain mapping system. The developed Airborne LiDAR Scanner (ALS) sys- tem consists of a high-precision GNSS receiver, an inertial measurement unit and a magnetic compass which are used to complement a LiDAR sensor in order to compute the terrain model. Evaluation of the accuracy of the generated 3D model is presented. Additionally, a comparison is provided between the terrain model generated from the developed ALS system and a model generated using a commer- cial photogrammetric software. Finally, the multi-echo capability of the used LiDAR sensor is evaluated in areas covered with dense vegetation. The ALS system and camera systems were mounted on-board an industrial unmanned helicopter of around 100 kilograms maximum take-off weight. Presented results are based on real flight-test data. [184] Patrick Doherty, Fredrik Heintz and Jonas Kvarnström. 2013. High-level Mission Specification and Planning for Collaborative Unmanned Aircraft Systems using Delegation. Unmanned Systems, 1(1):75–119. World Scientific. Automated specification, generation and execution of high level missions involving one or more heterogeneous unmanned aircraft systems is in its infancy. Much previous effort has been focused on the development of air vehicle platforms themselves together with the avionics and sensor subsystems that implement basic navigational skills. In order to increase the degree of autonomy in such systems so they can successfully participate in more complex mission scenarios such as those considered in emergency rescue that also include ongoing interactions with human operators, new architectural components and functionalities will be required to aid not only human operators in mission planning, but also the unmanned aircraft systems themselves in the automatic generation, execution and partial verification of mission plans to achieve mission goals. This article proposes a formal framework and architecture based on the unifying concept of delegation that can be used for the automated specification, generation and execution of high-level collaborative missions involving one or more air vehicles platforms and human operators. We describe an agent-based software architecture, a temporal logic based mission specification language, a distributed temporal planner and a task specification language that when integrated provide a basis for the generation, instantiation and execution of complex collaborative missions on heterogeneous air vehicle systems. A prototype of the framework is operational in a number of autonomous unmanned aircraft systems developed in our research lab. [183] Fredrik Heintz, Jonas Kvarnström and Patrick Doherty. 2013. Stream-Based Hierarchical Anchoring. Künstliche Intelligenz, 27(2):119–128. Springer. DOI: 10.1007/s13218-013-0239-2. Autonomous systems situated in the real world often need to recognize, track, and reason about various types of physical objects. In order to allow reasoning at a symbolic level, one must create and continuously maintain a correlation between symbols denoting physical objects and sensor data being collected about them, a process called anchoring.In this paper we present a stream-based hierarchical anchoring framework. A classification hierarchy is associated with expressive conditions for hypothesizing the type and identity of an object given streams of temporally tagged sensor data. The anchoring process constructs and maintains a set of object linkage structures representing the best possible hypotheses at any time. Each hypothesis can be incrementally generalized or narrowed down as new sensor data arrives. Symbols can be associated with an object at any level of classification, permitting symbolic reasoning on different levels of abstraction. The approach is integrated in the DyKnow knowledge processing middleware and has been applied to an unmanned aerial vehicle traffic monitoring application. [182] Håkan Warnquist, Jonas Kvarnström and Patrick Doherty. 2013. Exploiting Fully Observable and Deterministic Structures in Goal POMDPs. In Daniel Borrajo, Subbarao Kambhampati, Angelo Oddi, Simone Fratini, editors, Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS), pages 242–250. AAAI Press. ISBN: 978-1-57735-609-7. When parts of the states in a goal POMDP are fully observable and some actions are deterministic it is possibleto take advantage of these properties to efficiently generate approximate solutions. Actions that deterministically affect the fully observable component of the world state can be abstracted away and combined into macro actions, permitting a planner to converge more quickly. This processing can be separated from the main search procedure, allowing us to leverage existing POMDP solvers. Theoretical results show how a POMDP can be analyzed to identify the exploitable properties and formal guarantees are provided showing that the use of macro actions preserves solvability. The efficiency of the method is demonstrated with examples when used in combination with existing POMDP solvers. [181] Mikael Nilsson, Jonas Kvarnström and Patrick Doherty. 2013. Incremental Dynamic Controllability Revisited. In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press. ISBN: 978-1-57735-609-7. Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are determined by nature, as is often the case for actions in planning. As such networks are generated it is essential to verify that they are dynamically controllable – executable regardless of the outcomes of uncontrollable durations – and to convert them to a dispatchable form. The previously published FastIDC algorithm achieves this incrementally and can therefore be used efficiently during plan construction. In this paper we show that FastIDC is not sound when new constraints are added, sometimes labeling networks as dynamically controllable when they are not. We analyze the algorithm, pinpoint the cause, and show how the algorithm can be modified to correctly detect uncontrollable networks. 2012 [180] Patrick Doherty and John-Jules Ch. Meyer. 2012. On the Logic of Delegation - Relating Theory and Practice. In Fabio Paglieri, Luca Tummolini, Rino Falcone, Maria Miceli, editors, The Goals of Cognition: Essays in honour of Cristiano Castelfranchi, pages 467–496. College Publications. ISBN: 978-1848900943. Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=978-184... Research with collaborative robotic systems has much to gain by leveraging concepts and ideas from the areas of multi-agent systems and the social sciences. In this paper we propose an approach to formalizing and grounding important aspects of collaboration in a collaborative system shell for robotic systems. This is done primarily in terms of the concept of delegation, where delegation will be instantiated as a speech act. The formal characterization of the delegation speech act is based on a preformal theory of delegation proposed by Falcone and Castelfranchi. We show how the delegation speech act can in fact be used to formally ground an abstract characterization of delegation into a FIPA-compliant implementation in an agent-oriented language such as JADE, as part of a collaborative system shell for robotic systems. The collaborative system shell has been developed as a prototype and used in collaborative missions with multiple unmanned aerial vehicle systems. [179] Patrick Doherty, Fredrik Heintz and David Landén. 2012. A Distributed Task Specification Language for Mixed-Initiative Delegation. In Nirmit Desai, Alan Liu, Michael Winikoff, editors, Principles and Practice of Multi-Agent Systems: 13th International Conference, PRIMA 2010, Kolkata, India, November 12-15, 2010, Revised Selected Papers, pages 42–57. In series: Lecture Notes in Computer Science #7057. Springer Berlin/Heidelberg. ISBN: 978-3-642-25919-7, e-978-3-642-25920-3. DOI: 10.1007/978-3-642-25920-3_4. In the next decades, practically viable robotic/agent systems are going to be mixed-initiative in nature. Humans will request help from such systems and such systems will request help from humans in achieving the complex mission tasks required. Pragmatically, one requires a distributed task specification language to define tasks and a suitable data structure which satisfies the specification and can be used flexibly by collaborative multi-agent/robotic systems. This paper defines such a task specification language and an abstract data structure called Task Specification Trees which has many of the requisite properties required for mixed-initiative problem solving and adjustable autonomy in a distributed context. A prototype system has been implemented for this delegation framework and has been used practically with collaborative unmanned aircraft systems. [178] David Landén, Fredrik Heintz and Patrick Doherty. 2012. Complex Task Allocation in Mixed-Initiative Delegation: A UAV Case Study. In Nirmit Desai, Alan Liu, Michael Winikoff, editors, Principles and Practice of Multi-Agent Systems: 13th International Conference, PRIMA 2010, Kolkata, India, November 12-15, 2010, Revised Selected Papers, pages 288–303. In series: Lecture Notes in Computer Science #7057. Springer Berlin/Heidelberg. ISBN: 978-3-642-25919-7, e-978-3-642-25920-3. DOI: 10.1007/978-3-642-25920-3_20. Unmanned aircraft systems (UASs) are now becoming technologically mature enough to be integrated into civil society. An essential issue is principled mixed-initiative interaction between UASs and human operators. Two central problems are to specify the structure and requirements of complex tasks and to assign platforms to these tasks. We have previously proposed Task Specification Trees (TSTs) as a highly expressive specification language for complex multi-agent tasks that supports mixed-initiative delegation and adjustable autonomy. The main contribution of this paper is a sound and complete distributed heuristic search algorithm for allocating the individual tasks in a TST to platforms. The allocation also instantiates the parameters of the tasks such that all the constraints of the TST are satisfied. Constraints are used to model dependencies between tasks, resource usage as well as temporal and spatial requirements on complex tasks. Finally, we discuss a concrete case study with a team of unmanned aerial vehicles assisting in a challenging emergency situation. [177] L. Marconi, C. Melchiorri, M. Beetz, D. Pangercic, R. Siegwart, S. Leutenegger, R. Carloni, S. Stramigioli, H. Bruyninckx, Patrick Doherty, Alexander Kleiner, V. Lippiello, A. Finzi, B. Siciliano, A. Sala and N. Tomatis. 2012. The SHERPA project: Smart collaboration between humans and ground-aerial robots for improving rescuing activities in alpine environments. In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–4. IEEE. ISBN: 978-1-4799-0164-7, 978-1-4799-0163-0, 978-1-4799-0165-4. DOI: 10.1109/SSRR.2012.6523905. The goal of the paper is to present the foreseen research activity of the European project “SHERPA” whose activities will start officially on February 1th 2013. The goal of SHERPA is to develop a mixed ground and aerial robotic platform to support search and rescue activities in a real-world hostile environment, like the alpine scenario that is specifically targeted in the project. Looking into the technological platform and the alpine rescuing scenario, we plan to address a number of research topics about cognition and control. What makes the project potentially very rich from a scientific viewpoint is the heterogeneity and the capabilities to be owned by the different actors of the SHERPA system: the human rescuer is the “busy genius”, working in team with the ground vehicle, as the “intelligent donkey”, and with the aerial platforms, i.e. the “trained wasps” and “patrolling hawks”. Indeed, the research activity focuses on how the “busy genius” and the “SHERPA animals” interact and collaborate with each other, with their own features and capabilities, toward the achievement of a common goal. [176] Luc De Raedt, Christian Bessiere, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik Heintz and Peter Lucas. 2012. Proceedings of the 20th European Conference on Artificial Intelligence (ECAI). Conference Proceedings. In series: Frontiers in Artificial Intelligence and Applications #242. IOS Press. 1056 pages. ISBN: 978-1-61499-097-0. [175] Patrick Doherty and Fredrik Heintz. 2012. Delegation-Based Collaboration. In Proceedings of the 5th International Conference on Cognitive Systems (CogSys). [174] Patrick Doherty, Jonas Kvarnström and Andrzej Szalas. 2012. Temporal Composite Actions with Constraints. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 478–488. AAAI Press. ISBN: 978-1-57735-560-1, 978-1-57735-561-8. Link: http://www.aaai.org/ocs/index.php/KR/KR1... Complex mission or task specification languages play a fundamentally important role in human/robotic interaction. In realistic scenarios such as emergency response, specifying temporal, resource and other constraints on a mission is an essential component due to the dynamic and contingent nature of the operational environments. It is also desirable that in addition to having a formal semantics, the language should be sufficiently expressive, pragmatic and abstract. The main goal of this paper is to propose a mission specification language that meets these requirements. It is based on extending both the syntax and semantics of a well-established formalism for reasoning about action and change, Temporal Action Logic (TAL), in order to represent temporal composite actions with constraints. Fixpoints are required to specify loops and recursion in the extended language. The results include a sound and complete proof theory for this extension. To ensure that the composite language constructs are adequately grounded in the pragmatic operation of robotic systems, Task Specification Trees (TSTs) and their mapping to these constructs are proposed. The expressive and pragmatic adequacy of this approach is demonstrated using an emergency response scenario. 2011 [173] Gianpaolo Conte and Patrick Doherty. 2011. A Visual Navigation System for UAS Based on Geo-referenced Imagery. In International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXVIII-1/C22Proceedings of the International Conference on Unmanned Aerial Vehicle in Geomatics, Zurich, Switzerland, September 14-16, 2011. [172] Patrick Doherty, Fredrik Heintz and David Landén. 2011. A Delegation-Based Collaborative Robotic Framework. In Christian Guttmann, editor, Proceedings of the 3rd International Workshop on Collaborative Agents - Research and development. [171] Patrick Doherty, Fredrik Heintz and David Landén. 2011. A Delegation-Based Architecture for Collaborative Robotics. In Danny Weyns and Marie-Pierre Gleizes, editors, Agent-Oriented Software Engineering XI: 11th International Workshop, AOSE 2010, Toronto, Canada, May 10-11, 2010, Revised Selected Papers, pages 205–247. In series: Lecture Notes in Computer Science #6788. Springer Berlin/Heidelberg. ISBN: 978-3-642-22635-9. DOI: 10.1007/978-3-642-22636-6_13. Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=978-3-6... find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/12509689 Collaborative robotic systems have much to gain by leveraging results from the area of multi-agent systems and in particular agent-oriented software engineering. Agent-oriented software engineering has much to gain by using collaborative robotic systems as a testbed. In this article, we propose and specify a formally grounded generic collaborative system shell for robotic systems and human operated ground control systems. Collaboration is formalized in terms of the concept of delegation and delegation is instantiated as a speech act. Task Specification Trees are introduced as both a formal and pragmatic characterization of tasks and tasks are recursively delegated through a delegation process implemented in the collaborative system shell. The delegation speech act is formally grounded in the implementation using Task Specification Trees, task allocation via auctions and distributed constraint problem solving. The system is implemented as a prototype on Unmanned Aerial Vehicle systems and a case study targeting emergency service applications is presented. [170] Patrick Doherty and Fredrik Heintz. 2011. A Delegation-Based Cooperative Robotic Framework. In Proceedings of the IEEE International Conference on Robotics and Biomimetic, pages 2955–2962. IEEE conference proceedings. ISBN: 978-1-4577-2136-6. DOI: 10.1109/ROBIO.2011.6181755. Cooperative robotic systems, such as unmanned aircraft systems, are becoming technologically mature enough to be integrated into civil society. To gain practical use and acceptance, a verifiable, principled and well-defined foundation for interactions between human operators and autonomous systems is needed. In this paper, we propose and specify such a formally grounded collaboration framework. Collaboration is formalized in terms of the concept of delegation and delegation is instantiated as a speech act. Task Specification Trees are introduced as both a formal and pragmatic characterization of tasks and tasks are recursively delegated through a delegation process. The delegation speech act is formally grounded in the implementation using Task Specification Trees, task allocation via auctions and distributed constraint solving. The system is implemented as a prototype on unmanned aerial vehicle systems and a case study targeting emergency service applications is presented. [169] Patrick Doherty, Barbara Dunin-Keplicz and Andrzej Szalas. 2011. Tractable model checking for fragments of higher-order coalition logic. In Liz Sonenberg, Peter Stone, Kagan Tumer, Pinar Yolum, editors, Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, pages 743–750. AAAI Press. ISBN: 0-9826571-6-1, 978-0-9826571-6-4. Link: http://dl.acm.org/citation.cfm?id=203172... A number of popular logical formalisms for representing and reasoning about the abilities of teams or coalitions of agents have been proposed beginning with the Coalition Logic (CL) of Pauly. Ågotnes et al introduced a means of succinctly expressing quantification over coalitions without compromising the computational complexity of model checking in CL by introducing Quantified Coalition Logic (QCL). QCL introduces a separate logical language for characterizing coalitions in the modal operators used in QCL. Boella et al, increased the representational expressibility of such formalisms by introducing Higher-Order Coalition Logic (HCL), a monadic second-order logic with special set grouping operators. Tractable fragments of HCL suitable for efficient model checking have yet to be identified. In this paper, we relax the monadic restriction used in HCL and restrict ourselves to the diamond operator. We show how formulas using the diamond operator are logically equivalent to second-order formulas. This permits us to isolate and define well-behaved expressive fragments of second-order logic amenable to model-checking in PTime. To do this, we appeal to techniques used in deductive databases and quantifier elimination. In addition, we take advantage of the monotonicity of the effectivity function resulting in exponentially more succinct representation of models. The net result is identification of highly expressible fragments of a generalized HCL where model checking can be done efficiently in PTime. [168] Patrick Doherty, Tomasz Michalak, Jacek Sroka and Andrzej Szalas. 2011. Contextual Coalitional Games. In Mohua Banerjee, Anil Seth, editors, Proceedings of the 4th Indian Conference on Logic and its Applications (ICLA), pages 65–78. In series: Lecture Notes in Artificial Intelligence #6521. Springer Berlin/Heidelberg. DOI: 10.1007/978-3-642-18026-2_7. The study of cooperation among agents is of central interest in multi-agent systems research. A popular way to model cooperation is through coalitional game theory. Much research in this area has had limited practical applicability as regards real-world multi-agent systems due to the fact that it assumesdeterministic payoffs to coalitions and in addition does not apply to multi-agent environments that arestochastic in nature. In this paper, we propose a novel approach to modeling such scenarios where coalitional games will be contextualized through the use of logical expressions representing environmental and other state, and probability distributions will be placed on the space of contexts in order to model the stochastic nature of the scenarios. More formally, we present a formal representation language for representing contextualized coalitional games embedded in stochastic environments and we define and show how to compute expected Shapley values in such games in a computationally efficient manner. We present the value of the approach through an example involving robotics assistance in emergencies. [167] Mark Buller, Paul Cuddihy, Ernest Davis, Patrick Doherty, Finale Doshi-Velez, Esra Erdem, Douglas Fisher, Nancy Green, Knut Hinkelmann, James McLurkin, Mary Lou Maher, Rajiv Maheswaran, Sara Rubinelli, Nathan Schurr, Donia Scott, Dylan Shell, Pedro Szekely, Barbara Thoenssen and Arnold B Urken. 2011. Reports of the AAAI 2011 Spring Symposia. The AI Magazine, 32(3):119–127. AAAI Press. The Association for the Advancement of Artificial Intelligence presented the 2011 Spring Symposium Series Monday through Wednesday, March 21-23, 2011, at Stanford University. This report summarizes the eight symposia. 2010 [166] Patrick Doherty, Jonas Kvarnström, Fredrik Heintz, David Landén and Per-Magnus Olsson. 2010. Research with Collaborative Unmanned Aircraft Systems. In Gerhard Lakemeyer, Hector J. Levesque, Fiora Pirri, editors, Proceedings of the Dagstuhl Workshop on Cognitive Robotics. In series: Dagstuhl Seminar Proceedings #10081. Leibniz-Zentrum für Informatik. We provide an overview of ongoing research which targets development of a principled framework for mixed-initiative interaction with unmanned aircraft systems (UAS). UASs are now becoming technologically mature enough to be integrated into civil society. Principled interaction between UASs and human resources is an essential component in their future uses in complex emergency services or bluelight scenarios. In our current research, we have targeted a triad of fundamental, interdependent conceptual issues: delegation, mixed- initiative interaction and adjustable autonomy, that is being used as a basis for developing a principled and well-defined framework for interaction. This can be used to clarify, validate and verify different types of interaction between human operators and UAS systems both theoretically and practically in UAS experimentation with our deployed platforms. [165] Oleg Burdakov, Patrick Doherty, Kaj Holmberg and Per-Magnus Olsson. 2010. Optimal placement of UV-based communications relay nodes. Journal of Global Optimization, 48(4):511–531. Springer. DOI: 10.1007/s10898-010-9526-8. Note: The original publication is available at www.springerlink.com:Oleg Burdakov, Patrick Doherty, Kaj Holmberg and Per-Magnus Olsson, Optimal placement of UV-based communications relay nodes, 2010, Journal of Global Optimization, (48), 4, 511-531.http://dx.doi.org/10.1007/s10898-010-9526-8Copyright: Springer Science Business Mediahttp://www.springerlink.com/ We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem. [164] Piotr Rudol, Mariusz Wzorek and Patrick Doherty. 2010. Vision-based Pose Estimation for Autonomous Indoor Navigation of Micro-scale Unmanned Aircraft Systems. In Proceedings of the 2010 IEEE International Conference on Robotics and Automation (ICRA), pages 1913–1920. In series: Proceedings - IEEE International Conference on Robotics and Automation #2010. IEEE conference proceedings. ISBN: 978-1-4244-5038-1. DOI: 10.1109/ROBOT.2010.5509203. We present a navigation system for autonomous indoor flight of micro-scale Unmanned Aircraft Systems (UAS) which is based on a method for accurate monocular vision pose estimation. The method makes use of low cost artificial landmarks placed in the environment and allows for fully autonomous flight with all computation done on-board a UAS on COTS hardware. We provide a detailed description of all system components along with an accuracy evaluation and a time profiling result for the pose estimation method. Additionally, we show how the system is integrated with an existing micro-scale UAS and provide results of experimental autonomous flight tests. To our knowledge, this system is one of the first to allow for complete closed-loop control and goal-driven navigation of a micro-scale UAS in an indoor setting without requiring connection to any external entities. [163] Mariusz Wzorek, Jonas Kvarnström and Patrick Doherty. 2010. Choosing Path Replanning Strategies for Unmanned Aircraft Systems. In Ronen Brafman, Héctor Geffner, Jörg Hoffmann, Henry Kautz, editors, Proceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS), pages 193–200. AAAI Press. ISBN: 978-1-57735-449-9. Unmanned aircraft systems use a variety of techniques to plan collision-free flight paths given a map of obstacles and no- fly zones. However, maps are not perfect and obstacles may change over time or be detected during flight, which may in- validate paths that the aircraft is already following. Thus, dynamic in-flight replanning is required.Numerous strategies can be used for replanning, where the time requirements and the plan quality associated with each strategy depend on the environment around the original flight path. In this paper, we investigate the use of machine learn- ing techniques, in particular support vector machines, to choose the best possible replanning strategy depending on the amount of time available. The system has been implemented, integrated and tested in hardware-in-the-loop simulation with a Yamaha RMAX helicopter platform. [162] Fredrik Heintz, Jonas Kvarnström and Patrick Doherty. 2010. Stream-Based Reasoning in DyKnow. In Gerhard Lakemeyer and Hector J. Levesque and Fiora Pirri, editors, Proceedings of the Dagstuhl Workshop on Cognitive Robotics. In series: Dagstuhl Seminar Proceedings #10081. Leibniz-Zentrum für Informatik. The information available to modern autonomous systems is often in the form of streams. As the number of sensors and other stream sources increases there is a growing need for incremental reasoning about the incomplete content of sets of streams in order to draw relevant conclusions and react to new situations as quickly as possible. To act rationally, autonomous agents often depend on high level reasoning components that require crisp, symbolic knowledge about the environment. Extensive processing at many levels of abstraction is required to generate such knowledge from noisy, incomplete and quantitative sensor data. We define knowledge processing middleware as a systematic approach to integrating and organizing such processing, and argue that connecting processing components with streams provides essential support for steady and timely flows of information. DyKnow is a concrete and implemented instantiation of such middleware, providing support for stream reasoning at several levels. First, the formal kpl language allows the specification of streams connecting knowledge processes and the required properties of such streams. Second, chronicle recognition incrementally detects complex events from streams of more primitive events. Third, complex metric temporal formulas can be incrementally evaluated over streams of states. DyKnow and the stream reasoning techniques are described and motivated in the context of a UAV traffic monitoring application. [161] Fredrik Heintz, Jonas Kvarnström and Patrick Doherty. 2010. Stream-Based Middleware Support for Embedded Reasoning. In Proceedings of the AAAI Spring Symposium on Embedded Reasoning: Intelligence in Embedded Systems (ER). AAAI Press. ISBN: 978-157735458-1. For autonomous systems such as unmanned aerial vehicles to successfully perform complex missions, a great deal of embedded reasoning is required at varying levels of abstraction. In order to make use of diverse reasoning modules in such systems, issues of integration such as sensor data flow and information flow between such modules has to be taken into account. The DyKnow framework is a tool with a formal basis that pragmatically deals with many of the architectural issues which arise in such systems. This includes a systematic stream-based method for handling the sense-reasoning gap, caused by the wide difference in abstraction levels between the noisy data generally available from sensors and the symbolic, semantically meaningful information required by many high-level reasoning modules. DyKnow has proven to be quite robust and widely applicable to different aspects of hybrid software architectures for robotics.In this paper, we describe the DyKnow framework and show how it is integrated and used in unmanned aerial vehicle systems developed in our group. In particular, we focus on issues pertaining to the sense-reasoning gap and the symbol grounding problem and the use of DyKnow as a means of generating semantic structures representing situational awareness for such systems. We also discuss the use of DyKnow in the context of automated planning, in particular execution monitoring. [160] Fredrik Heintz, Jonas Kvarnström and Patrick Doherty. 2010. Stream-Based Reasoning Support for Autonomous Systems. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI). In series: Frontiers in Artificial Intelligence and Applications #215. IOS Press. ISBN: 978-1-60750-605-8. DOI: 10.3233/978-1-60750-606-5-183. For autonomous systems such as unmanned aerial vehicles to successfully perform complex missions, a great deal of embedded reasoning is required at varying levels of abstraction. To support the integration and use of diverse reasoning modules we have developed DyKnow, a stream-based knowledge processing middleware framework. By using streams, DyKnow captures the incremental nature of sensor data and supports the continuous reasoning necessary to react to rapid changes in the environment. DyKnow has a formal basis and pragmatically deals with many of the architectural issues which arise in autonomous systems. This includes a systematic stream-based method for handling the sense-reasoning gap, caused by the wide difference in abstraction levels between the noisy data generally available from sensors and the symbolic, semantically meaningful information required by many highlevel reasoning modules. As concrete examples, stream-based support for anchoring and planning are presented. [159] Fredrik Heintz and Patrick Doherty. 2010. Federated DyKnow, a Distributed Information Fusion System for Collaborative UAVs. In Proceedings of the 11th International Conference on Control, Automation, Robotics and Vision (ICARCV), pages 1063–1069. IEEE conference proceedings. ISBN: 978-1-4244-7814-9. DOI: 10.1109/ICARCV.2010.5707967. As unmanned aerial vehicle (UAV) applications are becoming more complex and covering larger physical areas there is an increasing need for multiple UAVs to cooperatively solve problems. To produce more complete and accurate information about the environment we present the DyKnow Federation framework for distributed fusion among collaborative UAVs. A federation is created and maintained using a multi-agent delegation framework which allows high-level specification and reasoning about resource bounded cooperative problem solving. When the federation is set up, local information is transparently shared between the agents according to specification. The work is presented in the context of a multi-UAV traffic monitoring scenario. [158] Jonas Kvarnström and Patrick Doherty. 2010. Automated Planning for Collaborative UAV Systems. In Proceedings of the 11th International Conference on Control, Automation, Robotics and Vision (ICARCV), pages 1078–1085. IEEE conference proceedings. ISBN: 978-1-4244-7813-2, 978-1-4244-7814-9. DOI: 10.1109/ICARCV.2010.5707969. IEEE Explore: http://ieeexplore.ieee.org/xpls/abs_all.... Mission planning for collaborative Unmanned Aircraft Systems (UAS:s) is a complex topic which involves trade-offs between the degree of centralization or decentralization required, the degree of abstraction in which plans are generated, and the degree to which such plans are distributed among participating UAS:s. In realistic environments such as those found in naturaland man-made catastrophes where emergency services personnelare involved, a certain degree of centralization and abstractionis necessary in order for those in charge to understand andeventually sign off on potential plans. It is also quite often thecase that unconstrained distribution of actions is inconsistentwith the loosely coupled interactions and dependencies whicharise between collaborating systems. In this article, we presenta new planning algorithm for collaborative UAS:s based oncombining ideas from forward chaining planning with partialorderplanning leading to a new hybrid partial order forwardchaining(POFC) framework which meets the requirements oncentralization, abstraction and distribution we find in realisticemergency services settings. [157] Per-Magnus Olsson, Jonas Kvarnström, Patrick Doherty, Oleg Burdakov and Kaj Holmberg. 2010. Generating UAV Communication Networks for Monitoring and Surveillance. In Proceedings of the 11th International Conference on Control, Automation, Robotics and Vision (ICARCV 2010), pages 1070–1077. IEEE conference proceedings. ISBN: 978-1-4244-7814-9. DOI: 10.1109/ICARCV.2010.5707968. An important use of unmanned aerial vehicles is surveillance of distant targets, where sensor information must quickly be transmitted back to a base station. In many cases, high uninterrupted bandwidth requires line-of-sight between sender and transmitter to minimize quality degradation. Communication range is typically limited, especially when smaller UAVs are used. Both problems can be solved by creating relay chains for surveillance of a single target, and relay trees for simultaneous surveillance of multiple targets. In this paper, we show how such chains and trees can be calculated. For relay chains we create a set of chains offering different trade-offs between the number of UAVs in the chain and the chain’s cost. We also show new results on how relay trees can be quickly calculated and then incrementally improved if necessary. Encouraging empirical results for improvement of relay trees are presented. [156] Håkan Warnquist, Jonas Kvarnström and Patrick Doherty. 2010. Iterative Bounding LAO*. In Helder Coelho, Rudi Studer and Mike Wooldridge, editors, ECAI 2010: 19th European Conference on Artificial Intelligence - Volume 215 Frontiers in Artificial Intelligence and Applications, pages 341–346. In series: Frontiers in Artificial Intelligence and Applications #215. IOS Press. ISBN: 978-1-60750-605-8 (print), 978-1-60750-606-5 (eBook). DOI: 10.3233/978-1-60750-606-5-341. Iterative Bounding LAO* is a new algorithm for epsilon- optimal probabilistic planning problems where an absorbing goal state should be reached at a minimum expected cost from a given initial state. The algorithm is based on the LAO* algorithm for finding optimal solutions in cyclic AND/OR graphs. The new algorithm uses two heuristics, one upper bound and one lower bound of the optimal cost. The search is guided by the lower bound as in LAO*, while the upper bound is used to prune search branches. The algorithm has a new mechanism for expanding search nodes, and while maintaining the error bounds, it may use weighted heuristics to reduce the size of the explored search space. In empirical tests on benchmark problems, Iterative Bounding LAO* expands fewer search nodes compared to state of the art RTDP variants that also use two-sided bounds. [155] Patrick Doherty and Andrzej Szalas. 2010. On the Correctness of Rough-Set Based Approximate Reasoning. In M. Szczuka, M. Kryszkiewicz, S. Ramanna, R. Jensen, Q. Hu, editors, Proceedings of the 7th International Conference on Rough Sets and Current Trends in Computing (RSCTC), pages 327–336. In series: Lecture Notes in Computer Science #6086. Springer. ISBN: 978-3-642-13528-6. DOI: 10.1007/978-3-642-13529-3_35. There is a natural generalization of an indiscernibility relation used in rough set theory, where rather than partitioning the universe of discourse into indiscernibility classes, one can consider a covering of the universe by similarity-based neighborhoods with lower and upper approximations of relations defined via the neighborhoods. When taking this step, there is a need to tune approximate reasoning to the desired accuracy. We provide a framework for analyzing self-adaptive knowledge structures. We focus on studying the interaction between inputs and output concepts in approximate reasoning. The problems we address are: -given similarity relations modeling approximate concepts, what are similarity relations for the output concepts that guarantee correctness of reasoning? -assuming that output similarity relations lead to concepts which are not accurate enough, how can one tune input similarities? [154] Oleg Burdakov, Patrick Doherty, Kaj Holmberg, Jonas Kvarnström and Per-Magnus Olsson. 2010. Relay Positioning for Unmanned Aerial Vehicle Surveillance. The international journal of robotics research, 29(8):1069–1087. Sage Publications. DOI: 10.1177/0278364910369463. When unmanned aerial vehicles (UAVs) are used for surveillance, information must often be transmitted to a base station in real time. However, limited communication ranges and the common requirement of free line of sight may make direct transmissions from distant targets impossible. This problem can be solved using relay chains consisting of one or more intermediate relay UAVs. This leads to the problem of positioning such relays given known obstacles, while taking into account a possibly mission-specific quality measure. The maximum quality of a chain may depend strongly on the number of UAVs allocated. Therefore, it is desirable to either generate a chain of maximum quality given the available UAVs or allow a choice from a spectrum of Pareto-optimal chains corresponding to different trade-offs between the number of UAVs used and the resulting quality. In this article, we define several problem variations in a continuous three-dimensional setting. We show how sets of Pareto-optimal chains can be generated using graph search and present a new label-correcting algorithm generating such chains significantly more efficiently than the best-known algorithms in the literature. Finally, we present a new dual ascent algorithm with better performance for certain tasks and situations. [153] Fredrik Heintz, Jonas Kvarnström and Patrick Doherty. 2010. Bridging the sense-reasoning gap: DyKnow - Stream-based middleware for knowledge processing. Advanced Engineering Informatics, 24(1):14–26. Elsevier. DOI: 10.1016/j.aei.2009.08.007. Engineering autonomous agents that display rational and goal-directed behavior in dynamic physical environments requires a steady flow of information from sensors to high-level reasoning components. However, while sensors tend to generate noisy and incomplete quantitative data, reasoning often requires crisp symbolic knowledge. The gap between sensing and reasoning is quite wide, and cannot in general be bridged in a single step. Instead, this task requires a more general approach to integrating and organizing multiple forms of information and knowledge processing on different levels of abstraction in a structured and principled manner. We propose knowledge processing middleware as a systematic approach to organizing such processing. Desirable properties are presented and motivated. We argue that a declarative stream-based system is appropriate for the required functionality and present DyKnow, a concrete implemented instantiation of stream-based knowledge processing middleware with a formal semantics. Several types of knowledge processes are defined and motivated in the context of a UAV traffic monitoring application. In the implemented application, DyKnow is used to incrementally bridge the sense-reasoning gap and generate partial logical models of the environment over which metric temporal logical formulas are evaluated. Using such formulas, hypotheses are formed and validated about the type of vehicles being observed. DyKnow is also used to generate event streams representing for example changes in qualitative spatial relations, which are used to detect traffic violations expressed as declarative chronicles. [152] Oleg Burdakov, Patrick Doherty, Kaj Holmberg, Jonas Kvarnström and Per-Magnus Olsson. 2010. Positioning Unmanned Aerial Vehicles As Communication Relays for Surveillance Tasks. In J. Trinkle, Y. Matsuoka and J.A. Castellanos, editors, Robotics: Science and Systems V, pages 257–264. MIT Press. ISBN: 978-0-262-51463-7. find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/12536749 Link to publication: http://www.roboticsproceedings.org/rss05... When unmanned aerial vehicles (UAVs) are used to survey distant targets, it is important to transmit sensor information back to a base station. As this communication often requires high uninterrupted bandwidth, the surveying UAV often needs afree line-of-sight to the base station, which can be problematic in urban or mountainous areas. Communication ranges may also belimited, especially for smaller UAVs. Though both problems can be solved through the use of relay chains consisting of one or more intermediate relay UAVs, this leads to a new problem: Where should relays be placed for optimum performance? We present two new algorithms capable of generating such relay chains, one being a dual ascent algorithm and the other a modification of the Bellman-Ford algorithm. As the priorities between the numberof hops in the relay chain and the cost of the chain may vary, wecalculate chains of different lengths and costs and let the ground operator choose between them. Several different formulations for edge costs are presented. In our test cases, both algorithms are substantially faster than an optimized version of the original Bellman-Ford algorithm, which is used for comparison. 2009 [151] Håkan Warnquist, Jonas Kvarnström and Patrick Doherty. 2009. Planning as Heuristic Search for Incremental Fault Diagnosis and Repair. In Proceedings of the Scheduling and Planning Applications Workshop (SPARK) at the 19th International Conference on Automated Planning and Scheduling (ICAPS). In this paper we study the problem of incremental fault diagnosis and repair of mechatronic systems where the task is to choose actions such that the expected cost of repair is minimal. This is done by interleaving acting with the generation of partial conditional plans used to decide the next action. A diagnostic model based on Bayesian Networks is used to update the current belief state after each action. The planner uses a simplified version of this model to update predicted belief states. We have tested the approach in the domain of troubleshooting heavy vehicles. Experiments show that a simplified model for planning improves performance when troubleshooting with limited time. [150] Oleg Burdakov, Kaj Holmberg, Patrick Doherty and Per-Magnus Olsson. 2009. Optimal placement of communications relay nodes. Technical Report. In series: LiTH-MAT-R #2009:3. Linköpings universitet. 21 pages. We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem. [149] Patrick Doherty and Jonas Kvarnström. 2009. Temporal Action Logics. In V. Lifschitz, F. van Harmelen, and F. Porter, editors, Handbook of Knowledge Representation, pages 709–757. In series: Foundations of Artificial Intelligence #3. Elsevier. ISBN: 978-0-444-52211-5. DOI: 10.1016/S1574-6526(07)03018-0. find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/hitlist?d=libris&q=9... The study of frameworks and formalisms for reasoning about action and change [67, 58, 61, 65, 70, 3, 57] has been central to the knowledge representation field almost from the inception of Artificial Intelligence as a general field of research [52, 56]. The phrase “Temporal Action Logics” represents a class of logics for reasoning about action and change that evolved from Sandewall’s book on Features and Fluents [61] and owes much to this ambitious project. There are essentially three major parts to Sandewall’s work. He first developed a narrative-based logical framework for specifying agent behavior in terms of action scenarios. The logical framework is state-based and uses explicit time structures. He then developed a formal framework for assessing the correctness (soundness and completeness) of logics for reasoning about action and change relative to a set of well-defined intended conclusions, where reasoning problems were classified according to their ontological or epistemological characteristics. Finally, he proposed a number of logics defined semantically in terms of definitions of preferential entailment1 and assessed their correctness using his assessment framework. [148] Martin Magnusson, David Landén and Patrick Doherty. 2009. Logical Agents that Plan, Execute, and Monitor Communication. In Proceedings of the 2nd Workshop on Logic and the Simulation of Interaction and Reasoning (LSIR-2). [147] Martin Magnusson and Patrick Doherty. 2009. Planning Speech Acts in a Logic of Action and Change. In Fredrik Heintz and Jonas Kvarnström, editors, The Swedish AI Society Workshop 2009, SAIS 2009, pages 39–48. In series: Linköping Electronic Conference Proceedings #35. Linköping University Electronic Press, Linköpings universitet. Fulltext: http://www.ep.liu.se/ecp/035/008/ecp0935... Cooperation is a complex task that necessarily involves communication and reasoning about others’ intentions and beliefs. Multi-agent communication languages aid designers of cooperating robots through standardized speech acts, sometimes including a formal semantics. But a more direct approach would be to have the robots plan both regular and communicative actions themselves. We show how two robots with heterogeneous capabilities can autonomously decide to cooperate when faced with a task that would otherwise be impossible. Request and inform speech acts are formulated in the same first-order logic of action and change as is used for regular actions. This is made possible by treating the contents of communicative actions as quoted formulas of the same language. The robot agents then use a natural deduction theorem prover to generate cooperative plans for an example scenario by reasoning directly with the axioms of the theory. [146] Patrick Doherty, Jonas Kvarnström and Fredrik Heintz. 2009. A Temporal Logic-based Planning and Execution Monitoring Framework for Unmanned Aircraft Systems. Autonomous Agents and Multi-Agent Systems, 19(3):332–377. Springer. DOI: 10.1007/s10458-009-9079-8. Research with autonomous unmanned aircraft systems is reaching a new degree of sophistication where targeted missions require complex types of deliberative capability integrated in a practical manner in such systems. Due to these pragmatic constraints, integration is just as important as theoretical and applied work in developing the actual deliberative functionalities. In this article, we present a temporal logic-based task planning and execution monitoring framework and its integration into a fully deployed rotor-based unmanned aircraft system developed in our laboratory. We use a very challenging emergency services application involving body identification and supply delivery as a vehicle for showing the potential use of such a framework in real-world applications. TALplanner, a temporal logic-based task planner, is used to generate mission plans. Building further on the use of TAL (Temporal Action Logic), we show how knowledge gathered from the appropriate sensors during plan execution can be used to create state structures, incrementally building a partial logical model representing the actual development of the system and its environment over time. We then show how formulas in the same logic can be used to specify the desired behavior of the system and its environment and how violations of such formulas can be detected in a timely manner in an execution monitor subsystem. The pervasive use of logic throughout the higher level deliberative layers of the system architecture provides a solid shared declarative semantics that facilitates the transfer of knowledge between different modules. [145] Fredrik Heintz, Jonas Kvarnström and Patrick Doherty. 2009. Stream Reasoning in DyKnow: A Knowledge Processing Middleware System. In Proceedings of the Stream Reasoning Workshop. In series: CEUR Workshop Proceedings #466. M. Jeusfeld c/o Redaktion Sun SITE, Informatik V, RWTH Aachen. The information available to modern autonomous systems is often in the form of streams. As the number of sensors and other stream sources increases there is a growing need for incremental reasoning about the incomplete content of sets of streams in order to draw relevant conclusions and react to new situations as quickly as possible. To act rationally, autonomous agents often depend on high level reasoning components that require crisp, symbolic knowledge about the environment. Extensive processing at many levels of abstraction is required to generate such knowledge from noisy, incomplete and quantitative sensor data. We define knowledge processing middleware as a systematic approach to integrating and organizing such processing, and argue that connecting processing components with streams provides essential support for steady and timely flows of information. DyKnow is a concrete and implemented instantiation of such middleware, providing support for stream reasoning at several levels. First, the formal KPL language allows the specification of streams connecting knowledge processes and the required properties of such streams. Second, chronicle recognition incrementally detects complex events from streams of more primitive events. Third, complex metric temporal formulas can be incrementally evaluated over streams of states. DyKnow and the stream reasoning techniques are described and motivated in the context of a UAV traffic monitoring application. [144] Martin Magnusson, Jonas Kvarnström and Patrick Doherty. 2009. Abductive Reasoning with Filtered Circumscription. In Proceedings of the IJCAI-09 Workshop on Nonmonotonic Reasoning, Action and Change (NRAC). UTSePress. ISBN: 978-0-9802840-7-2. For logical artificial intelligence to be truly useful,its methods must scale to problems of realistic size.An interruptible algorithm enables a logical agentto act in a timely manner to the best of its knowledge,given its reasoning so far. This seems necessaryto avoid analysis paralysis, trying to thinkof every potentiality, however unlikely, beforehand.These considerations prompt us to look for alternativereasoning mechanisms for filtered circumscription,a nonmonotonic reasoning formalism usede.g. by Temporal Action Logic and Event Calculus.We generalize Ginsberg’s circumscriptive theoremprover and describe an interruptible theoremprover based on abduction that has been used tounify planning and reasoning in a logical agent architecture. [143] Fredrik Heintz, Jonas Kvarnström and Patrick Doherty. 2009. A Stream-Based Hierarchical Anchoring Framework. In Proceedings of the IEEE/RSJ International Conference on Intelligent RObots and Systems (IROS). IEEE conference proceedings. ISBN: 978-1-4244-3803-7. DOI: 10.1109/IROS.2009.5354372. IEEE Xplore: http://ieeexplore.ieee.org/stamp/stamp.j... [142] Gianpaolo Conte and Patrick Doherty. 2009. Vision-Based Unmanned Aerial Vehicle Navigation Using Geo-Referenced Information. EURASIP Journal on Advances in Signal Processing, 2009(387308):1–18. Hindawi Publishing Corporation. DOI: 10.1155/2009/387308. This paper investigates the possibility of augmenting an Unmanned Aerial Vehicle (UAV) navigation system with a passive video camera in order to cope with long-term GPS outages. The paper proposes a vision-based navigation architecture which combines inertial sensors, visual odometry, and registration of the on-board video to a geo-referenced aerial image. The vision-aided navigation system developed is capable of providing high-rate and drift-free state estimation for UAV autonomous navigation without the GPS system. Due to the use of image-to-map registration for absolute position calculation, drift-free position performance depends on the structural characteristics of the terrain. Experimental evaluation of the approach based on offline flight data is provided. In addition the architecture proposed has been implemented on-board an experimental UAV helicopter platform and tested during vision-based autonomous flights. 2008 [141] Gianpaolo Conte and Patrick Doherty. 2008. Use of Geo-referenced Images with Unmanned Aerial Systems. In Workshop Proceedings of SIMPAR 2008, International Conference on Simulation, Modeling and Programming for Autonomous Robots. Venice(Italy) 2008 November,3-4., pages 444–454. ISBN: 978-88-95872-01-8. [140] Per Nyblom and Patrick Doherty. 2008. Towards Automatic Model Generation by Optimization. In Proceedings of the Tenth Scandinavian Conference on Artificial Intelligence (SCAI), pages 114–123. In series: Frontiers in Artificial Intelligence and Applications #173. IOS Press. ISBN: 978-1-58603-867-0, e-978-1-60750-335-4. Link to publication: http://www.booksonline.iospress.nl/Conte... The problem of automatically selecting simulation models for autonomous agents depending on their current intentions and beliefs is considered in this paper. The intended use of the models is for prediction, filtering, planning and other types of reasoning that can be performed with Simulation models. The parameters and model fragments of the resulting model are selected by formulating and solving a hybrid constrained optimization problem that captures the intuition of the preferred model when relevance information about the elements of the world being modelled is taken into consideration. A specialized version of the original optimization problem is developed that makes it possible to solve the continuous subproblem analytically in linear time. A practical model selection problem is discussed where the aim is to select suitable parameters and models for tracking dynamic objects. Experiments with randomly generated problem instances indicate that a hillclimbing search approach might be both efficient and provides reasonably good solutions compared to simulated annealing and hillclimbing with random restarts. [139] Gianpaolo Conte and Patrick Doherty. 2008. An Integrated UAV Navigation System Based on Aerial Image Matching. In IEEE Aerospace Conference 2008,2008, pages 3142–3151. In series: IEEE Aerospace Conference #??. IEEE. ISBN: 978-1-4244-1487-1, 978-1-4244-1488-8. DOI: 10.1109/AERO.2008.4526556. The aim of this paper is to explore the possibility of using geo-referenced satellite or aerial images to augment an Unmanned Aerial Vehicle (UAV) navigation system in case of GPS failure. A vision based navigation system which combines inertial sensors, visual odometer and registration of a UAV on-board video to a given geo-referenced aerial image has been developed and tested on real flight-test data. The experimental results show that it is possible to extract useful position information from aerial imagery even when the UAV is flying at low altitude. It is shown that such information can be used in an automated way to compensate the drift of the UAV state estimation which occurs when only inertial sensors and visual odometer are used. [138] Gianpaolo Conte, Maria Hempel, Piotr Rudol, David Lundström, Simone Duranti, Mariusz Wzorek and Patrick Doherty. 2008. High Accuracy Ground Target Geo-Location Using Autonomous Micro Aerial Vehicle Platforms. In Proceedings of the AIAA Guidance, Navigation, and Control Conference (GNC). AIAA. ISBN: 978-1-56347-945-8. This paper presents a method for high accuracy ground target localization using a Micro Aerial Vehicle (MAV) equipped with a video camera sensor. The proposed method is based on a satellite or aerial image registration technique. The target geo-location is calculated by registering the ground target image taken from an on-board video camera with a geo- referenced satellite image. This method does not require accurate knowledge of the aircraft position and attitude, therefore it is especially suitable for MAV platforms which do not have the capability to carry accurate sensors due to their limited payload weight and power resources. The paper presents results of a ground target geo-location experiment based on an image registration technique. The platform used is a MAV prototype which won the 3rd US-European Micro Aerial Vehicle Competition (MAV07). In the experiment a ground object was localized with an accuracy of 2.3 meters from a ight altitude of 70 meters. [137] Piotr Rudol and Patrick Doherty. 2008. Human Body Detection and Geolocalization for UAV Search and Rescue Missions Using Color and Thermal Imagery. In Proceedings of the IEEE Aerospace Conference, pages 1–8. In series: Aerospace Conference Proceedings #2008. IEEE. ISBN: 978-1-4244-1488-8 (online), 978-1-4244-1487-1 (print). DOI: 10.1109/AERO.2008.4526559. Recent advances in the field of Unmanned Aerial Vehicles (UAVs) make flying robots suitable platforms for carrying sensors and computer systems capable of performing advanced tasks. This paper presents a technique which allows detecting humans at a high frame rate on standard hardware onboard an autonomous UAV in a real-world outdoor environment using thermal and color imagery. Detected human positions are geolocated and a map of points of interest is built. Such a saliency map can, for example, be used to plan medical supply delivery during a disaster relief effort. The technique has been implemented and tested on-board the UAVTech1 autonomous unmanned helicopter platform as a part of a complete autonomous mission. The results of flight- tests are presented and performance and limitations of the technique are discussed. [136] Patrick Doherty and Andrzej Szalas. 2008. Reasoning with Qualitative Preferences and Cardinalities Using Generalized Circumscription. In Gerhard Brewka, Jérôme Lang, editors, Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 560–570. AAAI Press. ISBN: 978-1-57735-384-3. The topic of preference modeling has recently attracted the interest of a number of sub-disciplines in artificial intelligence such as the nonmonotonic reasoning and action and change communities. The approach in these communities focuses on qualitative preferences and preference models which provide more natural representations from a~commonsense perspective. In this paper, we show how generalized circumscription can be used as a highly expressive framework for qualitative preference modeling. Generalized circumscription proposed by Lifschitz allows for predicates (and thus formulas) to be minimized relative to arbitrary pre-orders (reflexive and transitive). Although it has received little attention, we show how it may be used to model and reason about elaborate qualitative preference relations. One of the perceived weaknesses with any type of circumscription is the 2nd-order nature of the representation. The paper shows how a large variety of preference theories represented using generalized circumscription can in fact be reduced to logically equivalent first-order theories in a constructive way. Finally, we also show how preference relations represented using general circumscription can be extended with cardinality constraints and when these extensions can also be reduced to logically equivalent first-order theories. [135] Fredrik Heintz and Patrick Doherty. 2008. DyKnow Federations: Distributing and Merging Information Among UAVs. In Proceedings of the 11th International Conference on Information Fusion (FUSION). IEEE conference proceedings. ISBN: 978-3-8007-3092-6. As unmanned aerial vehicle (UAV) applications become more complex and versatile there is an increasing need to allow multiple UAVs to cooperate to solve problems which are beyond the capability of each individual UAV. To provide more complete and accurate information about the environment we present a DyKnow federation framework for information integration in multi-node networks of UAVs. A federation is created and maintained using a multiagent delegation framework and allows UAVs to share local information as well as process information from other UAVs as if it were local using the DyKnow knowledge processing middleware framework. The work is presented in the context of a multi UAV traffic monitoring scenario. [134] Martin Magnusson and Patrick Doherty. 2008. Temporal Action Logic for Question Answering in an Adventure Game. In Artificial General Intelligence, AGI 2008, pages 236–247. In series: Frontiers in Artificial Intelligence and Applications #15. IOS Press. ISBN: 978-1-58603-833-5. Inhabiting the complex and dynamic environments of modern computer games with autonomous agents capable of intelligent timely behaviour is a significant research challenge. We illustrate this using Our own attempts to build a practical agent architecture on it logicist foundation. In the ANDI-Land adventure game concept players solve puzzles by eliciting information from computer characters through natural language question answering. While numerous challenges immediately presented themselves, they took on a form of concrete and accessible problems to solve, and we present some of our initial solutions. We conclude that games, due to their demand for human-like computer characters with robust and independent operation in large simulated worlds, might serve as excellent test beds for research towards artificial general intelligence. [133] Martin Magnusson, David Landén and Patrick Doherty. 2008. Planning, Executing, and Monitoring Communication in a Logic-Based Multi-Agent System. In ECAI 2008, pages 933–934. In series: Frontiers in Artificial Intelligence and Applications #178. IOS Press. ISBN: 978-1-58603-891-5. DOI: 10.3233/978-1-58603-891-5-933. [132] Martin Magnusson and Patrick Doherty. 2008. Deductive Planning with Inductive Loops. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 528–534. AAAI Press. ISBN: 978-1-57735-384-3. Agents plan to achieve and maintain goals. Maintenance that requires continuous action excludes the representation of plans as finite sequences of actions. If there is no upper bound on the number of actions, a simple list of actions would be infinitely long. Instead, a compact representation requires some form of looping construct. We look at a specific temporally extended maintenance goal, multiple target video surveillance, and formalize it in Temporal Action Logic. The logic's representation of time as the natural numbers suggests using mathematical induction to deductively plan to satisfy temporally extended goals. Such planning makes use of a sound and useful, but incomplete, induction rule that compactly represents the solution as a recursive fixpoint formula. Two heuristic rules overcome the problem of identifying a sufficiently strong induction hypothesis and enable an automated solution to the surveillance problem that satisfies the goal indefinitely. [131] Martin Magnusson and Patrick Doherty. 2008. Logical Agents for Language and Action. In 4th International Artificial Intelligence and Interactive Digital Entertainment Conference AIIDE 2008,2008. AAAI Press. ISBN: 978-1-57735-391-1. [130] Fredrik Heintz, Jonas Kvarnström and Patrick Doherty. 2008. Bridging the Sense-Reasoning Gap: DyKnow - A Middleware Component for Knowledge Processing. In Martin Hulse and Manfred Hild, editors, IROS Workshop on Current Software Frameworks in Cognitive Robotics Integrating Different Computational Paradigms. Note: No proceedings, but CD Developing autonomous agents displaying rational and goal-directed behavior in a dynamic physical environment requires the integration of both sensing and reasoning components. Due to the different characteristics of these components there is a gap between sensing and reasoning. We believe that this gap can not be bridged in a single step with a single technique. Instead, it requires a more general approach to integrating components on many different levels of abstraction and organizing them in a structured and principled manner. In this paper we propose knowledge processing middleware as a systematic approach for organizing such processing. Desirable properties of such middleware are presented and motivated. We then go on to argue that a declarative streambased system is appropriate to provide the desired functionality. Finally, DyKnow, a concrete example of stream-based knowledge processing middleware that can be used to bridge the sense-reasoning gap, is presented. Different types of knowledge processes and components of the middleware are described and motivated in the context of a UAV traffic monitoring application. [129] Jonas Kvarnström, Fredrik Heintz and Patrick Doherty. 2008. A Temporal Logic-Based Planning and Execution Monitoring System. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press. ISBN: 978-1-57735-386-7, 978-1-57735-387-4. As no plan can cover all possible contingencies, the ability to detect failures during plan execution is crucial to the robustness of any autonomous system operating in a dynamic and uncertain environment. In this paper we present a general planning and execution monitoring system where formulas in an expressive temporal logic specify the desired behavior of a system and its environment. A unified domain description for planning and monitoring provides a solid shared declarative semantics permitting the monitoring of both global and operator-specific conditions. During plan execution, an execution monitor subsystem detects violations of monitor formulas in a timely manner using a progression algorithm on incrementally generated partial logical models. The system has been integrated on a fully deployed autonomous unmanned aircraft system. Extensive empirical testing has been performed using a combination of actual flight tests and hardware-in-the-loop simulations in a number of different mission scenarios. [128] Per-Magnus Olsson and Patrick Doherty. 2008. The Observer Algorithm For Visibility Approximation. In 10th Scandinavian Conference on Artificial Intelligence, SCAI 2008, pages 3–11. In series: Frontiers in Artificial Intelligence and Applications #173. IOS Press. ISBN: 978-1-58603-867-0, e-978-1-60750-335-4. Link to paper: http://books.google.se/books?id=eju691VM... We present a novel algorithm for visibility approximation that is substantially faster than ray casting based algorithms. The algorithm does not require extensive preprocessing or specialized hardware as most other algorithms do. We test this algorithm in several settings: rural, mountainous and urban areas, with different view ranges and grid cell sizes. By changing the size of the grid cells that the algorithm uses, it is possible to tailor the algorithm between speed and accuracy. [127] Piotr Rudol, Mariusz Wzorek, Gianpaolo Conte and Patrick Doherty. 2008. Micro unmanned aerial vehicle visual servoing for cooperative indoor exploration. In Proceedings of the IEEE Aerospace Conference. In series: Aerospace Conference Proceedings #2008. IEEE conference proceedings. ISBN: 978-1-4244-1487-1. DOI: 10.1109/AERO.2008.4526558. Recent advances in the field of micro unmanned aerial vehicles (MAVs) make flying robots of small dimensions suitable platforms for performing advanced indoor missions. In order to achieve autonomous indoor flight a pose estimation technique is necessary. This paper presents a complete system which incorporates a vision-based pose estimation method to allow a MAV to navigate in indoor environments in cooperation with a ground robot. The pose estimation technique uses a lightweight light emitting diode (LED) cube structure as a pattern attached to a MAV. The pattern is observed by a ground robot's camera which provides the flying robot with the estimate of its pose. The system is not confined to a single location and allows for cooperative exploration of unknown environments. It is suitable for performing missions of a search and rescue nature where a MAV extends the range of sensors of the ground robot. The performance of the pose estimation technique and the complete system is presented and experimental flights of a vertical take-off and landing (VTOL) MAV are described. [126] Fredrik Heintz, Jonas Kvarnström and Patrick Doherty. 2008. Knowledge Processing Middleware. In S. Carpin, I. Noda, E. Pagello, M. Reggiani and O. von Stryk, editors, Proceedings of the 1st International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR), pages 147–158. In series: Lecture Notes in Computer Science #5325. Springer. ISBN: 978-3-540-89075-1 (print), 978-3-540-89076-8 (online). DOI: 10.1007/978-3-540-89076-8_17. Developing autonomous agents displaying rational and goal-directed behavior in a dynamic physical environment requires the integration of a great number of separate deliberative and reactive functionalities. This integration must be built on top of a solid foundation of data, information and knowledge having numerous origins, including quantitative sensors and qualitative knowledge databases. Processing is generally required on many levels of abstraction and includes refinement and fusion of noisy sensor data and symbolic reasoning. We propose the use of knowledge processing middleware as a systematic approach for organizing such processing. Desirable properties of such middleware are presented and motivated. We then argue that a declarative stream-based system is appropriate to provide the desired functionality. Different types of knowledge processes and components of the middleware are described and motivated in the context of a UAV traffic monitoring application. Finally DyKnow, a concrete example of stream-based knowledge processing middleware, is briefly described. 2007 [125] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2007. Communication between agents with heterogeneous perceptual capabilities. Information Fusion, 8(1):56–69. Elsevier. DOI: 10.1016/j.inffus.2005.05.006. In real world applications robots and software agents often have to be equipped with higher level cognitive functions that enable them to reason, act and perceive in changing, incompletely known and unpredictable environments. One of the major tasks in such circumstances is to fuse information from various data sources. There are many levels of information fusion, ranging from the fusing of low level sensor signals to the fusing of high level, complex knowledge structures. In a dynamically changing environment even a single agent may have varying abilities to perceive its environment which are dependent on particular conditions. The situation becomes even more complex when different agents have different perceptual capabilities and need to communicate with each other. In this paper, we propose a framework that provides agents with the ability to fuse both low and high level approximate knowledge in the context of dynamically changing environments while taking account of heterogeneous and contextually limited perceptual capabilities. To model limitations on an agent's perceptual capabilities we introduce the idea of partial tolerance spaces. We assume that each agent has one or more approximate databases where approximate relations are represented using lower and upper approximations on sets. Approximate relations are generalizations of rough sets. It is shown how sensory and other limitations can be taken into account when constructing and querying approximate databases for each respective agent. Complex relations inherit the approximativeness of primitive relations used in their definitions. Agents then query these databases and receive answers through the filters of their perceptual limitations as represented by (partial) tolerance spaces and approximate queries. The techniques used are all tractable. © 2005 Elsevier B.V. All rights reserved. [124] Patrick Doherty and Andrzej Szalas. 2007. A correspondence framework between three-valued logics and similarity-based approximate reasoning. Fundamenta Informaticae, 75(1-4):179–193. IOS Press. This paper focuses on approximate reasoning based on the use of similarity spaces. Similarity spaces and the approximated relations induced by them are a generalization of the rough set-based approximations of Pawlak [17, 18]. Similarity spaces are used to define neighborhoods around individuals and these in turn are used to define approximate sets and relations. In any of the approaches, one would like to embed such relations in an appropriate logic which can be used as a reasoning engine for specific applications with specific constraints. We propose a framework which permits a formal study of the relationship between approximate relations, similarity spaces and three-valued logics. Using ideas from correspondence theory for modal logics and constraints on an accessibility relation, we develop an analogous framework for three-valued logics and constraints on similarity relations. In this manner, we can provide a tool which helps in determining the proper three-valued logical reasoning engine to use for different classes of approximate relations generated via specific types of similarity spaces. Additionally, by choosing a three-valued logic first, the framework determines what constraints would be required on a similarity relation and the approximate relations induced by it. Such information would guide the generation of approximate relations for specific applications. [123] Mariusz Wzorek and Patrick Doherty. 2007. A framework for reconfigurable path planning for autonomous unmanned aerial vehicles. Manuscript (preprint). [122] Simone Duranti, Gianpaolo Conte, David Lundström, Piotr Rudol, Mariusz Wzorek and Patrick Doherty. 2007. LinkMAV, a prototype rotary wing micro aerial vehicle. In 17th IFAC Symposium on Automatic Control in Aerospace,2007. Elsevier. [121] Patrick Doherty, Barbara Dunin-Keplicz and Andrzej Szalas. 2007. Dynamics of approximate information fusion. In Proceedings of the International Conference on Rough Sets and Emerging Intelligent Systems Paradigms (RSEISP), pages 668–677. In series: Lecture Notes in Artificial Intelligence #4585. Springer Berlin/Heidelberg. ISBN: 978-3-540-73450-5. DOI: 10.1007/978-3-540-73451-2_70. The multi-agent system paradigm has proven to be a useful means of abstraction when considering distributed systems with interacting components. It is often the case that each component may be viewed as an intelligent agent with specific and often limited perceptual capabilities. It is also the case that these agent components may be used as information sources and such sources may be aggregated to provide global information about particular states, situations or activities in the embedding environment. This paper investigates a framework for information fusion based on the use of generalizations of rough set theory and the use of dynamic logic as a basis for aggregating similarity relations among objects where the similarity relations represent individual agents perceptual capabilities or limitations. As an added benefit, it is shown how this idea may also be integrated into description logics. [120] Patrick Doherty and John-Jules Meyer. 2007. Towards a delegation framework for aerial robotic mission scenarios. In Proceedings of the 11th International Workshop on Cooperative Information Agents (CIA), pages 5–26. Springer Berlin/Heidelberg. ISBN: 978-3-540-75118-2. DOI: 10.1007/978-3-540-75119-9_2. The concept of delegation is central to an understanding of the interactions between agents in cooperative agent problem-solving contexts. In fact, the concept of delegation offers a means for studying the formal connections between mixed-initiative problem-solving, adjustable autonomy and cooperative agent goal achievement. In this paper, we present an exploratory study of the delegation concept grounded in the context of a relatively complex multi-platform Unmanned Aerial Vehicle (UAV) catastrophe assistance scenario, where UAVs must cooperatively scan a geographic region for injured persons. We first present the scenario as a case study, showing how it is instantiated with actual UAV platforms and what a real mission implies in terms of pragmatics. We then take a step back and present a formal theory of delegation based on the use of 2APL and KARO. We then return to the scenario and use the new theory of delegation to formally specify many of the communicative interactions related to delegation used in achieving the goal of cooperative UAV scanning. The development of theory and its empirical evaluation is integrated from the start in order to ensure that the gap between this evolving theory of delegation and its actual use remains closely synchronized as the research progresses. The results presented here may be considered a first iteration of the theory and ideas. [119] Patrick Doherty and Piotr Rudol. 2007. A UAV search and rescue scenario with human body detection and geolocalization. In Proceedings of the 20th Australian Joint Conference on Artificial Intelligence (AI). Springer Berlin/Heidelberg. ISBN: 978-3-540-76926-2. The use of Unmanned Aerial Vehicles (UAVs) which can operate autonomously in dynamic and complex operational environments is becoming increasingly more common. The UAVTech Lab, is pursuing a long term research endeavour related to the development of future aviation systems which try and push the envelope in terms of using and integrating high-level deliberative or AI functionality with traditional reactive and control components in autonomous UAV systems. In order to carry on such research, one requires challenging mission scenarios which force such integration and development. In this paper, one of these challenging emergency services mission scenarios is presented. It involves search and rescue for injured civilians by UAVs. In leg I of the mission, UAVs scan designated areas and try to identify injured civilians. In leg II of the mission, an attempt is made to deliver medical and other supplies to identified victims. We show how far we have come in implementing and executing such a challenging mission in realistic urban scenarios. [118] Luis Mejias, Pascual Campoy, Iván F. Mondragón and Patrick Doherty. 2007. Stereo visual system for autonomous air vehicle navigation. In 6th IFAC Symposium on Intelligent Autonomous Vehicles (2007) Intelligent Autonomous Vehicles, Volume# 6 | Part# 1, pages 203–208. In series: IFAC Proceedings series #??. Elsevier. ISBN: 978-3-902661-65-4. DOI: 10.3182/20070903-3-FR-2921.00037. We present a system to estimate the altitude and motion of an aerial vehicle using a stereo visual system. The system has been initially tested on a ground robot and the novelty lays on its application and robustness validation in an UAV, where vibrations and rapid environmental changes take place. The two main functionalities are height estimation and visual odometry. The system first detects and tracks salient points in the scene. Depth to the plane containing the features is calculated matching features between left and right images then using the disparity principle. Motion is recovered tracking pixels from one frame to the next one finding its visual displacement and resolving camera rotation and translation by a least-square method. We present results from different experimental trials on the two platforms comparing and discussing the results regarding the trajectories calculated by the visual odometry and the onboard helicopter state estimation. [117] Fredrik Heintz, Piotr Rudol and Patrick Doherty. 2007. From Images to Traffic Behavior - A UAV Tracking and Monitoring Application. In Proceedings of the 10th International Conference on Information Fusion (FUSION). IEEE conference proceedings. ISBN: 978-0-662-45804-3, 978-0-662-47830-0. DOI: 10.1109/ICIF.2007.4408103. Link: http://www.ida.liu.se/~frehe/publication... An implemented system for achieving high level situation awareness about traffic situations in an urban area is described. It takes as input sequences of color and thermal images which are used to construct and maintain qualitative object structures and to recognize the traffic behavior of the tracked vehicles in real time. The system is tested both in simulation and on data collected during test flights. To facilitate the signal to symbol transformation and the easy integration of the streams of data from the sensors with the GIS and the chronicle recognition system, DyKnow, a stream-based knowledge processing middleware, is used. It handles the processing of streams, including the temporal aspects of merging and synchronizing streams, and provides suitable abstractions to allow high level reasoning and narrow the sense reasoning gap. [116] Fredrik Heintz, Piotr Rudol and Patrick Doherty. 2007. Bridging the Sense-Reasoning Gap Using DyKnow: A Knowledge Processing Middleware Framework. In Joachim Hertzberg, Michael Beetz and Roman Englert, editors, Proceedings of the 30th Annual German Conference on Artificial Intelligence (KI), pages 460–463. In series: Lecture Notes in Computer Science #4667. Springer. ISBN: 978-3-540-74564-8. DOI: 10.1007/978-3-540-74565-5_40. Link: http://www.ida.liu.se/~frehe/publication... To achieve complex missions an autonomous unmanned aerial vehicle (UAV) operating in dynamic environments must have and maintain situational awareness. This can be achieved by continually gathering information from many sources, selecting the relevant information for current tasks, and deriving models about the environment and the UAV itself. It is often the case models suitable for traditional control, are not sufficient for deliberation. The need for more abstract models creates a sense-reasoning gap. This paper presents DyKnow, a knowledge processing middleware framework, and shows how it supports bridging the gap in a concrete UAV traffic monitoring application. In the example, sequences of color and thermal images are used to construct and maintain qualitative object structures. They model the parts of the environment necessary to recognize traffic behavior of tracked vehicles in real-time. The system has been implemented and tested in simulation and on data collected during flight tests. [115] Martin Magnusson and Patrick Doherty. 2007. Deductive Planning with Temporal Constraints. In Commonsense 2007, the 8th International Symposium on Logical Formalizations of Commonsense Reasoning,2007. AAAI Press. ISBN: 978-1-57735-314-0. Link: http://www.ucl.ac.uk/commonsense07/paper... Temporal Action Logic is a well established logical formalism for reasoning about action and change using an explicit time representation that makes it suitable for applications that involve complex temporal reasoning. We take advantage of constraint satisfaction technology to facilitate such reasoning through temporal constraint networks. Extensions are introduced that make generation of action sequences possible, thus paving the road for interesting applications in deductive planning. The extended formalism is encoded as a logic program that is able to realize a least commitment strategy that generates partial order plans in the context of both qualitative and quantitative temporal constraints. 2006 [114] Alexander Kleiner, Christian Dornhege, Rainer Kümmerle, Michael Ruhnke, Bastian Steder, Bernhard Nebel, Patrick Doherty, Mariusz Wzorek, Piotr Rudol, Gianpaolo Conte, Simone Duranti and David Lundström. 2006. RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany). In RoboCup 2006 (CDROM Proceedings), Team Description Paper, Rescue Robot League. Note: (1st place in the autonomy competition) This paper describes the approach of the RescueRobots Freiburg team, which is a team of students from the University of Freiburg that originates from the former CS Freiburg team (RoboCupSoccer) and the ResQ Freiburg team (RoboCupRescue Simulation). Furthermore we introduce linkMAV, a micro aerial vehicle platform. Our approach covers RFID-based SLAM and exploration, autonomous detection of relevant 3D structures, visual odometry, and autonomous victim identification. Furthermore, we introduce a custom made 3D Laser Range Finder (LRF) and a novel mechanism for the active distribution of RFID tags. [113] Klas Nordberg, Patrick Doherty, Per-Erik Forssén, Johan Wiklund and Per Andersson. 2006. A flexible runtime system for image processing in a distributed computational environment for an unmanned aerial vehicle. International Journal of Pattern Recognition and Artificial Intelligence, 20(5):763–780. DOI: 10.1142/S0218001406004867. A runtime system for implementation of image processing operations is presented. It is designed for working in a flexible and distributed environment related to the software architecture of a newly developed UAV system. The software architecture can be characterized at a coarse scale as a layered system, with a deliberative layer at the top, a reactive layer in the middle, and a processing layer at the bottom. At a finer scale each of the three levels is decomposed into sets of modules which communicate using CORBA, allowing system development and deployment on the UAV to be made in a highly flexible way. Image processing takes place in a dedicated module located in the process layer, and is the main focus of the paper. This module has been designed as a runtime system for data flow graphs, allowing various processing operations to be created online and on demand by the higher levels of the system. The runtime system is implemented in Java, which allows development and deployment to be made on a wide range of hardware/software configurations. Optimizations for particular hardware platforms have been made using Java's native interface. [112] Per Olof Pettersson and Patrick Doherty. 2006. Probabilistic roadmap based path planning for an autonomous unmanned helicopter. Journal of Intelligent & Fuzzy Systems, 17(4):395–405. IOS Press. The emerging area of intelligent unmanned aerial vehicle (UAV) research has shown rapid development in recent years and offers a great number of research challenges for artificial intelligence. For both military and civil applications, there is a desire to develop more sophisticated UAV platforms where the emphasis is placed on development of intelligent capabilities. Imagine a mission scenario where a UAV is supplied with a 3D model of a region containing buildings and road structures and is instructed to fly to an arbitrary number of building structures and collect video streams of each of the building's respective facades. In this article, we describe a fully operational UAV platform which can achieve such missions autonomously. We focus on the path planner integrated with the platform which can generate collision free paths autonomously during such missions. Both probabilistic roadmap-based (PRM) and rapidly exploring random trees-based (RRT) algorithms have been used with the platform. The PRM-based path planner has been tested together with the UAV platform in an urban environment used for UAV experimentation. [111] Fredrik Heintz and Patrick Doherty. 2006. A knowledge processing middleware framework and its relation to the JDL data fusion model. Journal of Intelligent & Fuzzy Systems, 17(4):335–351. IOS Press. Any autonomous system embedded in a dynamic and changing environment must be able to create qualitative knowledge and object structures representing aspects of its environment on the fly from raw or preprocessed sensor data in order to reason qualitatively about the environment and to supply such state information to other nodes in the distributed network in which it is embedded. These structures must be managed and made accessible to deliberative and reactive functionalities whose successful operation is dependent on being situationally aware of the changes in both the robotic agent's embedding and internal environments. DyKnow is a knowledge processing middleware framework which provides a set of functionalities for contextually creating, storing, accessing and processing such structures. The framework is implemented and has been deployed as part of a deliberative/reactive architecture for an autonomous unmanned aerial vehicle. The architecture itself is distributed and uses real-time CORBA as a communications infrastructure. We describe the system and show how it can be used to create more abstract entity and state representations of the world which can then be used for situation awareness by an unmanned aerial vehicle in achieving mission goals. We also show that the framework is a working instantiation of many aspects of the JDL data fusion model. [110] Patrick Doherty, John Mylopoulos and Christopher Welty. 2006. Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning. Conference Proceedings. AAAI Press. ISBN: 978-1-57735-281-5. he National Conference on Artificial Intelligence remains the bellwether for research in artificial intelligence. Leading AI researchers and practitioners as well as scientists and engineers in related fields present theoretical, experimental, and empirical results, covering a broad range of topics that include principles of cognition, perception, and action; the design, application, and evaluation of AI algorithms and systems; architectures and frameworks for classes of AI systems; and analyses of tasks and domains in which intelligent systems perform. The Innovative Applications of Artificial Intelligence conference highlights successful applications of AI technology; explores issues, methods, and lessons learned in the development and deployment of AI applications; and promotes an interchange of ideas between basic and applied AI. This volume presents the proceedings of the latest conferences, held in July, 2006. [109] Martin Magnusson and Patrick Doherty. 2006. Deductive Planning with Temporal Constraints using TAL. In Proceedings of the International Symposium on Practical Cognitive Agents and Robots (PCAR). UWA Press. ISBN: 1-74052-130-7. DOI: 10.1145/1232425.1232444. Temporal Action Logic is a well established logical formalism for reasoning about action and change using an explicit time representation that makes it suitable for applications that involve complex temporal reasoning. We take advantage of constraint satisfaction technology to facilitate such reasoning through temporal constraint networks. Extensions are introduced that make generation of action sequences possible, thus paving the road for interesting applications in deductive planning. The extended formalism is encoded as a logic program that is able to realize a least commitment strategy that generates partial order plans in the context of both qualitative and quantitative temporal constraints. [108] Mariusz Wzorek, David Landén and Patrick Doherty. 2006. GSM Technology as a Communication Media for an Autonomous Unmanned Aerial Vehicle. In Proceedings of the 21st Bristol International UAV Systems Conference (UAVS). University of Bristol, Department of Aerospace engineering. ISBN: 0-9552644-0-5. Note: ISBN: 0-9552644-0-5 [107] Mariusz Wzorek, Gianpaolo Conte, Piotr Rudol, Torsten Merz, Simone Duranti and Patrick Doherty. 2006. From Motion Planning to Control - A Navigation Framework for an Autonomous Unmanned Aerial Vehicle. In Proceedings of the 21st Bristol UAV Systems Conference (UAVS). Link to Ph.D. Thesis: http://urn.kb.se/resolve?urn=urn:nbn:se:... The use of Unmanned Aerial Vehicles (UAVs) which can operate autonomously in dynamic and complex operational environments is becoming increasingly more common. While the application domains in which they are currently used are still predominantly military in nature, in the future we can expect wide spread usage in thecivil and commercial sectors. In order to insert such vehicles into commercial airspace, it is inherently important that these vehicles can generate collision-free motion plans and also be able to modify such plans during theirexecution in order to deal with contingencies which arise during the course of operation. In this paper, wepresent a fully deployed autonomous unmanned aerial vehicle, based on a Yamaha RMAX helicopter, whichis capable of navigation in urban environments. We describe a motion planning framework which integrates two sample-based motion planning techniques, Probabilistic Roadmaps and Rapidly Exploring Random Treestogether with a path following controller that is used during path execution. Integrating deliberative services, suchas planners, seamlessly with control components in autonomous architectures is currently one of the major open problems in robotics research. We show how the integration between the motion planning framework and thecontrol kernel is done in our system.Additionally, we incorporate a dynamic path reconfigurability scheme. It offers a surprisingly efficient method for dynamic replanning of a motion plan based on unforeseen contingencies which may arise during the execution of a plan. Those contingencies can be inserted via ground operator/UAV interaction to dynamically change UAV flight paths on the fly. The system has been verified through simulation and in actual flight. We present empirical results of the performance of the framework and the path following controller. [106] Mariusz Wzorek and Patrick Doherty. 2006. The WITAS UAV Ground System Interface Demonstration with a Focus on Motion and Task Planning. In Software Demonstrations at the International Conference on Automated Planning Scheduling (ICAPS-SD), pages 36–37. The Autonomous UAV Technologies Laboratory at Linköping University, Sweden, has been developing fully autonomous rotor-based UAV systems in the mini- and micro-UAV class. Our current system design is the result of an evolutionary process based on many years of developing, testing and maintaining sophisticated UAV systems. In particular, we have used the Yamaha RMAX helicopter platform(Fig. 1) and developed a number of micro air vehicles from scratch. [105] Mariusz Wzorek and Patrick Doherty. 2006. Reconfigurable Path Planning for an Autonomous Unmanned Aerial Vehicle. In Derek Long, Stephen F. Smith, Daniel Borrajo, Lee McCluskey, editors, Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS), pages 438–441. AAAI Press. ISBN: 978-1-57735-270-9. In this paper, we present a motion planning framework for a fully deployed autonomous unmanned aerial vehicle which integrates two sample-based motion planning techniques, Probabilistic Roadmaps and Rapidly Exploring Random Trees. Additionally, we incorporate dynamic reconfigurability into the framework by integrating the motion planners with the control kernel of the UAV in a novel manner with little modification to the original algorithms. The framework has been verified through simulation and in actual flight. Empirical results show that these techniques used with such a framework offer a surprisingly efficient method for dynamically reconfiguring a motion plan based on unforeseen contingencies which may arise during the execution of a plan. The framework is generic and can be used for additional platforms. [104] Mariusz Wzorek and Patrick Doherty. 2006. Reconfigurable Path Planning for an Autonomous Unmanned Aerial Vehicle. In ICHIT 2006 - International Conference on Hybrid Information Technology,2006. [103] Patrick Doherty, Witold Lukaszewicz, Andrzej Skowron and Andrzej Szalas. 2006. Knowledge Representation Techniques.: a rough set approach. Book. In series: Studies in Fuzziness and Soft Computing #202. Springer. 342 pages. ISBN: 978-3-540-33518-4, 3-540-33518-8. DOI: 10.1007/3-540-33519-6. find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/hitlist?d=libris&q=9... The basis for the material in this book centers around a long term research project with autonomous unmanned aerial vehicle systems. One of the main research topics in the project is knowledge representation and reasoning. The focus of the research has been on the development of tractable combinations of approximate and nonmonotonic reasoning systems. The techniques developed are based on intuitions from rough set theory. Efforts have been made to take theory into practice by instantiating research results in the context of traditional relational database or deductive database systems. This book contains a cohesive, self-contained collection of many of the theoretical and applied research results that have been achieved in this project and for the most part pertain to nonmonotonic and approximate reasoning systems developed for an experimental unmanned aerial vehicle system used in the project. This book should be of interest to the theoretician and applied researcher alike and to autonomous system developers and software agent and intelligent system developers. [102] Patrick Doherty, Martin Magnusson and Andrzej Szalas. 2006. Approximate Databases: A support tool for approximate reasoning. Journal of applied non-classical logics, 16(1-2):87–118. Éditions Hermès-Lavoisier. DOI: 10.3166/jancl.16.87-117. Note: Special issue on implementation of logics This paper describes an experimental platform for approximate knowledge databases called the Approximate Knowledge Database (AKDB), based on a semantics inspired by rough sets. The implementation is based upon the use of a standard SQL database to store logical facts, augmented with several query interface layers implemented in JAVA through which extensional, intensional and local closed world nonmonotonic queries in the form of crisp or approximate logical formulas can be evaluated tractably. A graphical database design user interface is also provided which simplifies the design of databases, the entering of data and the construction of queries. The theory and semantics for AKDBs is presented in addition to application examples and details concerning the database implementation. 2005 [101] Patrick Doherty, Andrzej Szalas and Witold Lukaszewicz. 2005. Similarity, approximations and vagueness. In Dominik Slezak, Guoyin Wang, Marcin S. Szczuka, Ivo Düntsch, Yiyu Yao, editors, Proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing (RSFDGrC), pages 541–550. In series: Lecture Notes in Artificial Intelligence #3641. Springer. ISBN: 3-540-28653-5. DOI: 10.1007/11548669_56. The relation of similarity is essential in understanding and developing frameworks for reasoning with vague and approximate concepts. There is a wide spectrum of choice as to what properties we associate with similarity and such choices determine the nature of vague and approximate concepts defined in terms of these relations. Additionally, robotic systems naturally have to deal with vague and approximate concepts due to the limitations in reasoning and sensor capabilities. Halpern [1] introduces the use of subjective and objective states in a modal logic formalizing vagueness and distinctions in transitivity when an agent reasons in the context of sensory and other limitations. He also relates these ideas to a solution to the Sorities and other paradoxes. In this paper, we generalize and apply the idea of similarity and tolerance spaces [2,3,4,5], a means of constructing approximate and vague concepts from such spaces and an explicit way to distinguish between an agent’s objective and subjective states. We also show how some of the intuitions from Halpern can be used with similarity spaces to formalize the above-mentioned Sorities and other paradoxes. [100] Fredrik Heintz and Patrick Doherty. 2005. A knowledge processing middleware framework and its relation to the JDL data fusion model. In The 8th International Conference on Information Fusion,2005. [99] Mariusz Wzorek and Patrick Doherty. 2005. Reconfigurable path planning for an autonomous unmanned aerial vehicle. In National Swedish Workshop on Autonomous Systems, SWAR 05,2005. [98] Mariusz Wzorek and Patrick Doherty. 2005. Preliminary report: Reconfigurable path planning for an autonomous unmanned aerial vehicle. In Proceedings of the 24th Annual Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG). [97] Patrick Doherty. 2005. Knowledge representation and unmanned aerial vehicles. In Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT), pages 9–16. IEEE Computer Society. ISBN: 0-7695-2416-8. DOI: 10.1109/IAT.2005.93. Knowledge representation technologies play a fundamental role in any autonomous system that includes deliberative capability and that internalizes models of its internal and external environments. Integrating both high- and low-end autonomous functionality seamlessly in autonomous architectures is currently one of the major open problems in robotics research. UAVs offer especially difficult challenges in comparison with ground robotic systems due to the often tight time constraints and safety considerations that must be taken into account. This article provides an overview of some of the knowledge representation technologies and deliberative capabilities developed for a fully deployed autonomous unmanned aerial vehicle system to meet some of these challenges. [96] Fredrik Heintz and Patrick Doherty. 2005. A Knowledge processing Middleware Framework and its Relation to the JDL Data Fusion model. In SWAR 05,2005, pages 50–51. [95] Fredrik Heintz and Patrick Doherty. 2005. A Knowledge processing Middleware Framework and its Relation to the JDL Data Fusion model. In 3rd joint SAIS-SSL event on Artificial Intelligence an Learning Systems,2005. Mälardalens University. [94] Martin Magnusson, Patrick Doherty and Andrzej Szalas. 2005. An Experimental Platform for Approximate Databases. In 3rd joint SAIS-SSL event on Artificial Intelligence and Learning Systems,2005. [93] Per Olof Pettersson and Patrick Doherty. 2005. Probabilistic Roadmap Based Path Planning for an Autonomous Unmanned Helicopter. In Peter Funk, Thorsteinn Rögnvaldsson and Ning Xiong, editors, Proceedings of the 3rd joint SAIS-SSLS event on Artificial Intelligence and Learning Systems (SAIS-SSLS). Mälardalen University. The emerging area of intelligent unmanned aerialvehicle (UAV) research has shown rapid development in recentyears and offers a great number of research challenges for artificialintelligence. For both military and civil applications, thereis a desire to develop more sophisticated UAV platforms wherethe emphasis is placed on development of intelligent capabilities.Imagine a mission scenario where a UAV is supplied with a 3Dmodel of a region containing buildings and road structures andis instructed to fly to an arbitrary number of building structuresand collect video streams of each of the building’s respectivefacades. In this article, we describe a fully operational UAVplatform which can achieve such missions autonomously. Wefocus on the path planner integrated with the platform which cangenerate collision free paths autonomously during such missions.It is based on the use of probabilistic roadmaps. The path plannerhas been tested together with the UAV platform in an urbanenvironment used for UAV experimentation. 2004 [92] Fredrik Heintz and Patrick Doherty. 2004. DyKnow: A Framework for Processing Dynamic Knowledge and Object Structures in Autonomous Systems. In Proceedings of the Second Joint SAIS/SSLS Workshop. [91] Patrick Doherty, Steven Kertes, Martin Magnusson and Andrzej Szalas. 2004. Towards a logical analysis of biochemical pathways. In José Júlio Alferes and João Alexandre Leite, editors, Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA), pages 667–679. In series: Lecture Notes in Computer Science #3229. Springer. ISBN: 978-3-540-23242-1. DOI: 10.1007/978-3-540-30227-8_55. Biochemical pathways or networks are generic representations used to model many different types of complex functional and physical interactions in biological systems. Models based on experimental results are often incomplete, e.g., reactions may be missing and only some products are observed. In such cases, one would like to reason about incomplete network representations and propose candidate hypotheses, which when represented as additional reactions, substrates, products, would complete the network and provide causal explanations for the existing observations. In this paper, we provide a logical model of biochemical pathways and show how abductive hypothesis generation may be used to provide additional information about incomplete pathways. Hypothesis generation is achieved using weakest and strongest necessary conditions which represent these incomplete biochemical pathways and explain observations about the functional and physical interactions being modeled. The techniques are demonstrated using metabolism and molecular synthesis examples. [90] Fredrik Heintz and Patrick Doherty. 2004. DyKnow: An approach to middleware for knowledge processing. Journal of Intelligent & Fuzzy Systems, 15(1):3–13. IOS Press. Any autonomous system embedded in a dynamic and changing environment must be able to create qualitative knowledge and object structures representing aspects of its environment on the fly from raw or preprocessed sensor data in order to reason qualitatively about the environment. These structures must be managed and made accessible to deliberative and reactive functionalities which are dependent on being situationally aware of the changes in both the robotic agent's embedding and internal environment. DyKnow is a software framework which provides a set of functionalities for contextually accessing, storing, creating and processing such structures. The system is implemented and has been deployed in a deliberative/reactive architecture for an autonomous unmanned aerial vehicle. The architecture itself is distributed and uses real-time CORBA as a communications infrastructure. We describe the system and show how it can be used in execution monitoring and chronicle recognition scenarios for UAV applications. [89] Ubbo Visser and Patrick Doherty. 2004. Issues in Designing Physical Agents for Dynamic Real-Time Environments: World Modeling, Planning, Learning, and Communicating. The AI Magazine, 25(2):137–138. AAAI Press. This article discusses a workshop held in conjunction with the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), held in Acapulco, Mexico, on 11 August 2003. [88] Patrick Doherty. 2004. Advanced Research with Autonomous Unmanned Aerial Vehicles. In Proceedings of the 9th International Conference on the Principles of Knowledge Representation and Reasoning, pages 731–732. AAAI Press. ISBN: 978-1-57735-199-3. The emerging area of intelligent unmanned aerial vehicle (UAV) research has shown rapid development in recent years and offers a great number of research challenges for artificial intelligence and knowledge representation. For both military and civilian applications, there is a desire to develop more sophisticated UAV platforms where the emphasis is placed on intelligent capabilities and their integration in complex distributed software architectures. Such architectures should support the integration of deliberative, reactive and control functionalities in addition to the UAV’s integration with larger network centric systems. In my talk I will present some of the research and results from a long term basic research project with UAVs currently being pursued at Linköping University, Sweden. The talk will focus on knowledge representation techniques used in the project and the support for these techniques provided by the software architecture developed for our UAV platform, a Yamaha RMAX helicopter. Additional focus will be placed on some of the planning and execution monitoring functionality developed for our applications in the areas of traffic monitoring, surveying and photogrammetry and emergency services assistance. [87] Per Olof Pettersson and Patrick Doherty. 2004. Probabilistic Roadmap Based Path Planning for an Autonomous Unmanned Aerial Vehicle. In ICAPS-04 Workshop on Connecting Planning Theory with Practice,2004, pages 49–55. [86] Patrick Doherty, Patrik Haslum, Fredrik Heintz, Torsten Merz, Per Nyblom, Tommy Persson and Björn Wingman. 2004. A Distributed Architecture for Autonomous Unmanned Aerial Vehicle Experimentation. In 7th International Symposium on Distributed Autonomous Robotic Systems,2004. LAAS. [85] Fredrik Heintz and Patrick Doherty. 2004. Managing Dynamic Object Structures using Hypothesis Generation and Validation. In AAAI Workshop on Anchoring Symbols to Sensor Data,2004, pages 54–62. AAAI Press. [84] Fredrik Heintz and Patrick Doherty. 2004. DyKnow: A Framework for Processing Dynamic Knowledge and Object Structures in Autonomous Systems. In Barbara Dunin-Keplicz, Andrzej Jankowski, Andrzej Skowron, Marcin Szczuka, editors, Proceedings of the International Workshop on Monitoring, Security, and Rescue Techniques in Multi-Agent Systems (MSRAS), pages 479–492. In series: Advances in Soft Computing #28. Springer. ISBN: 978-3540232452. DOI: 10.1007/3-540-32370-8_37. Any autonomous system embedded in a dynamic and changing environment must be able to create qualitative knowledge and object structures representing aspects of its environment on the fly from raw or preprocessed sensor data in order to reason qualitatively about the environment. These structures must be managed and made accessible to deliberative and reactive functionalities which are dependent on being situationally aware of the changes in both the robotic agent’s embedding and internal environment. DyKnow is a software framework which provides a set of functionalities for contextually accessing, storing, creating and processing such structures. The system is implemented and has been deployed in a deliberative/reactive architecture for an autonomous unmanned aerial vehicle. The architecture itself is distributed and uses real-time CORBA as a communications infrastructure. We describe the system and show how it can be used in execution monitoring and chronicle recognition scenarios for UAV applications. [83] Patrick Doherty, Steven Kertes, Martin Magnusson and Andrzej Szalas. 2004. Towards a Logical Analysis of Biochemical Reactions (Extended abstract). In Ramon López de Mántaras, Lorenza Saitta, editors, Proceedings of the 16th European Conference on Artificial Intelligence (ECAI), pages 997–998. IOS Press. ISBN: 1-58603-452-9. We provide a logical model of biochemical reactions and show how hypothesis generation using weakest sufficient and strongest necessary conditions may be used to provide additional information in the context of an incomplete model of metabolic pathways. [82] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2004. Approximate Databases and Query Techniques for Agents with Heterogenous Perceptual Capabilities. In Proceedings of the 7th International Conference on Information Fusion, pages 175–182. ISIF. ISBN: 91-7056-115-X. In this paper, we propose a framework that provides software and robotic agents with the ability to ask approximate questions to each other in the context of heterogeneous and contextually limited perceptual capabilities. The framework focuses on situations where agents have varying ability to perceive their environments. These limitations on perceptual capability are formalized using the idea of tolerance spaces. It is assumed that each agent has one or more approximate databases where approximate relations are represented using intuitions from rough set theory. It is shown how sensory and other limitations can be taken into account when constructing approximate databases for each respective agent. Complex relations inherit the approximativeness inherent in the sensors and primitive relations used in their definitions. Agents then query these databases and receive answers through the filters of their perceptual limitations as represented by tolerance spaces and approximate queries. The techniques used are all tractable. [81] Patrick Doherty and Andrzej Szalas. 2004. On the Correspondence between Approximations and Similarity. In Shusaku Tsumoto, Roman Slowinski, Jan Komorowski and Jerzy W. Grzymala-Busse, editors, Proceedings of the International Conference on Rough Sets and Current Trends in Computing (RSCTC), pages 143–152. In series: Lecture Notes in Computer Science #3066. Springer. DOI: 10.1007/978-3-540-25929-9_16. This paper focuses on the use and interpretation of approximate databases where both rough sets and indiscernibility partitions are generalized and replaced by approximate relations and similarity spaces. Similarity spaces are used to define neighborhoods around individuals and these in turn are used to define approximate sets and relations. There is a wide spectrum of choice as to what properties the similarity relation should have and how this affects the properties of approximate relations in the database. In order to make this interaction precise, we propose a technique which permits specification of both approximation and similarity constraints on approximate databases and automatic translation between them. This technique provides great insight into the relation between similarity and approximation and is similar to that used in modal correspondence theory. In order to automate the translations, quantifier elimination techniques are used. [80] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2004. Approximative Query Techniques for Agents with Heterogeneous Ontologies and Perceptive Capabilities. In Didier Dubois, Christopher A. Welty, Mary-Anne Williams, editors, Proceedings of the 9th International Conference on the Principles of Knowledge Representation and Reasoning, pages 459–468. AAAI Press. ISBN: 978-1-57735-199-3. In this paper, we propose a framework that provides software and robotic agents with the ability to ask approximate questions to each other in the context of heterogeneous ontologies and heterogeneous perceptive capabilities.The framework combines the use of logic-based techniques with ideas from approximate reasoning. Initial queries by an agent are transformed into approximate queries using weakest sufficient and strongest necessary conditions on the query and are interpreted as lower and upper approximations on the query. Once the base communication ability is provided, the framework is extended to situations where there is not only a mismatch between agent ontologies, but the agents have varying ability to perceive their environments. This will affect each agent’s ability to ask and interpret results of queries. Limitations on perceptive capability are formalized using the idea of tolerance spaces. [79] Patrick Doherty, Jaroslaw Kachniarz and Andrzej Szalas. 2004. Using Contextually Closed Queries for Local Closed-World Reasoning in Rough Knowledge Databases. In Andrzej Skowron,Lech Polkowski ,Sankar K Pal, editors, Rough-Neural Computing: Techniques for Computing with Words, pages 219–250. In series: Cognitive Technologies #??. Springer. ISBN: 978-3-540-43059-9, 35-4043-059-8. find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/14144444 find book in another country/hitta boken i ett annat land: http://www.worldcat.org/title/rough-neur... Soft computing comprises various paradigms dedicated to approximately solving real-world problems, e.g., in decision making, classification or learning; among these paradigms are fuzzy sets, rough sets, neural networks, and genetic algorithms.It is well understood now in the soft computing community that hybrid approaches combining various paradigms provide very promising attempts to solving complex problems. Exploiting the potential and strength of both neural networks and rough sets, this book is devoted to rough-neurocomputing which is also related to the novel aspect of computing based on information granulation, in particular to computing with words. It provides foundational and methodological issues as well as applications in various fields. [78] Patrick Doherty, Witold Lukaszewicz, Andrzej Skowron and Andrzej Szalas. 2004. Approximation Transducers and Trees: A Technique for Combining Rough and Crisp Knowledge. In Andrzej Skowron,Lech Polkowski ,Sankar K Pal, editors, Rough-Neural Computing: Techniques for Computing with Words, pages 189–218. In series: Cognitive Technologies #??. Springer. ISBN: 978-3-540-43059-9, 35-4043-059-8. find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/14144444 find book in another country/hitta boken i ett annat land: http://www.worldcat.org/search?qt=worldc... Soft computing comprises various paradigms dedicated to approximately solving real-world problems, e.g., in decision making, classification or learning; among these paradigms are fuzzy sets, rough sets, neural networks, and genetic algorithms.It is well understood now in the soft computing community that hybrid approaches combining various paradigms provide very promising attempts to solving complex problems. Exploiting the potential and strength of both neural networks and rough sets, this book is devoted to rough-neurocomputing which is also related to the novel aspect of computing based on information granulation, in particular to computing with words. It provides foundational and methodological issues as well as applications in various fields. 2003 [77] Patrick Doherty, W. Lukaszewicz, Skowron Andrzej and Andrzej Szalas. 2003. Knowledge Representation and Approximate Reasoning. Conference Proceedings. In series: Fundamenta Informaticae #2003(57):2-4. IOS Press. Note: Special Issue [76] Erik Sandewall, Patrick Doherty, Oliver Lemon and Stanley Peters. 2003. Words at the Right Time: Real-Time Dialogues with the WITAS Unmanned Aerial Vehicle. In Proceedings of the 26th German Conference on Artificial Intelligence (KI), pages 52–63. In series: Lecture Notes in Computer Science #2821. Springer Verlag. DOI: 10.1007/978-3-540-39451-8_5. The WITAS project addresses the design of an intelligent, autonomous UAV (Unmanned Aerial Vehicle), in our case a helicopter. Its dialogue-system subprojects address the design of a deliberative system for natural-language and graphical dialogue with that robotic UAV. This raises new issues both for dialogue and for reasoning in real time. The following topics have been particularly important for us in various stages of the work in these subprojects: - spatiotemporal reference in the dialogue, including reference to past events and to planned or expected, future events - mixed initiative in the dialogue architecture of a complex system consisting of both dialogue-related components (speech, grammar, etc) and others (simulation, event recognition, interface to robot) and more recently as well - identification of a dialogue manager that is no more complex than what is required by the application - uniform treatment of different types of events, including the robot's own actions, observed events, communication events, and dialogue-oriented deliberation events - a logic of time, action, and spatiotemporal phenomena that facilitates the above. This paper gives a brief overview of the WITAS project as a whole, and then addresses the approaches that have been used and that are presently being considered in the work on two generations of dialogue subsystems. [75] Patrick Doherty, A Skowron, Witold Lukaszewicz and Andrzej Szalas. 2003. 1st International Workshop on Knowledge Representation and Approximate Reasoning (KR&AR). [74] Patrick Doherty, M Grabowski, Witold Lukaszewicz and Andrzej Szalas. 2003. Towards a framework for approximate ontologies. Fundamenta Informaticae, 57(2-4):147–165. IOS Press. Currently, there is a great deal of interest in developing tools for the generation and use of ontologies on the WWW. These knowledge structures are considered essential to the success of the semantic web, the next phase in the evolution of the WWW. Much recent work with ontologies assumes that the concepts used as building blocks are crisp as opposed to approximate. It is a premise of this paper that approximate concepts and ontologies will become increasingly more important as the semantic web becomes a reality. We propose a framework for specifying, generating and using approximate ontologies. More specifically, (1) a formal framework for defining approximate concepts, ontologies and operations on approximate concepts and ontologies is presented. The framework is based on intuitions from rough set theory, (2) algorithms for automatically generating approximate ontologies from traditional crisp ontologies or from large data sets together with additional knowledge are presented. The knowledge will generally be related to similarity measurements between individual objects in the data sets, or constraints of a logical nature which rule out particular constellations of concepts and dependencies in generated ontologies. The techniques for generating approximate ontologies are parameterizable. The paper provides specific instantiations and examples. [73] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2003. On mutual understanding among communicating agents. In B. Dunin-Keplicz and R. Verbrugge, editors, Proceedings of the International Workshop on Formal Approaches to Multi-Agent Systems (FAMAS), pages 83–97. [72] Patrick Doherty and et al. 2003. 2003 AAAI Spring Symposium Series. The AI Magazine, 24(3):131–140. AAAI Press. The American Association for Artificial Intelligence, in cooperation with Stanford University’s Department of Computer Science, presented the 2003 Spring Symposium Series, Monday through Wednesday, 24–26 March 2003, at Stanford University. The titles of the eight symposia were Agent-Mediated Knowledge Management, Computational Synthesis: From Basic Building Blocks to High- Level Functions, Foundations and Applications of Spatiotemporal Reasoning (FASTR), Human Interaction with Autonomous Systems in Complex Environments, Intelligent Multimedia Knowledge Management, Logical Formalization of Commonsense Reasoning, Natural Language Generation in Spoken and Written Dialogue, and New Directions in Question-Answering Motivation. [71] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2003. Tolerance Spaces and Approximative Representational Structures. In Proceedings of the 26th German Conference on Artificial Intelligence (KI), pages 475–489. In series: Lecture Notes in Computer Science #2821. Springer. DOI: 10.1007/978-3-540-39451-8_35. In traditional approaches to knowledge representation, notions such as tolerance measures on data, distance between objects or individuals, and similarity measures between primitive and complex data structures are rarely considered. There is often a need to use tolerance and similarity measures in processes of data and knowledge abstraction because many complex systems which have knowledge representation components such as robots or software agents receive and process data which is incomplete, noisy, approximative and uncertain. This paper presents a framework for recursively constructing arbitrarily complex knowledge structures which may be compared for similarity, distance and approximativeness. It integrates nicely with more traditional knowledge representation techniques and attempts to bridge a gap between approximate and crisp knowledge representation. It can be viewed in part as a generalization of approximate reasoning techniques used in rough set theory. The strategy that will be used is to define tolerance and distance measures on the value sets associated with attributes or primitive data domains associated with particular applications. These tolerance and distance measures will be induced through the different levels of data and knowledge abstraction in complex representational structures. Once the tolerance and similarity measures are in place, an important structuring generalization can be made where the idea of a tolerance space is introduced. Use of these ideas is exemplified using two application domains related to sensor modeling and communication between agents. [70] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2003. Information Granules for Intelligent Knowledge Structures. In Guoyin Wang, Qing Liu, Yiyu Yao, Andrzej Skowron, editors, Proceedings of the 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (RSFDGrC), pages 405–412. In series: Lecture Notes in Computer Science #2639. Springer. ISBN: 978-3-540-14040-5. DOI: 10.1007/3-540-39205-X_68. The premise of this paper is that the acquisition, aggregation, merging and use of information requires some new ideas, tools and techniques which can simplify the construction, analysis and use of what we call ephemeral knowledge structures. Ephemeral knowledge structures are used and constructed by granular agents. Each agent contains its own granular information structure and granular information structures of agents can be combined together. The main concept considered in this paper is an information granule. An information granule is a concise conceptual unit that can be integrated into a larger information infrastructure consisting of other information granules and dependencies between them. The novelty of this paper is that it provides a concise and formal definition of a particular view of information granule and its associated operators, as required in advanced knowledge representation applications. 2002 [69] John-Jules Meyer and Patrick Doherty. 2002. Preferential Action Semantics. In John-Jules Ch Meyer; Jan Treur, editor, Handbook of Defeasible Reasoning and Uncertainty Management Systems: Volume 7:: Agent-Based Defeasible Control in Dynamic Environments. In series: Handbook of Defeasible Reasoning and Uncertainty Management Systems #7. Kluwer. ISBN: 978-1-4020-0834-4, 14-02-0-0834-1. find book in another country/hitta boken i ett annat land: http://www.worldcat.org/search?q=Handboo... This last volume of the Handbook of Defeasible Reasoning and Uncertainty Management Systems is - together with Volume 6 - devoted to the topics Reasoning and Dynamics, covering both the topics of \"Dynamics of Reasoning,\" where reasoning is viewed as a process, and \"Reasoning about Dynamics,\" which must be understood as pertaining to how both designers of, and agents within dynamic systems may reason about these systems. The present volume presents work done in this context and is more focused on \"reasoning about dynamics,\" viz. how (human and artificial) agents reason about (systems in) dynamic environments in order to control them. In particular modelling frameworks and generic agent models for modelling these dynamic systems and formal approaches to these systems such as logics for agents and formal means to reason about agent-based and compositional systems, and action & change more in general are considered. [68] Klas Nordberg, Patrick Doherty, Gunnar Farnebäck, Per-Erik Forssén, Gösta Granlund, Anders Moe and Johan Wiklund. 2002. Vision for a UAV helicopter. In International Conference on Intelligent Robots and Systems (IROS), Workshop on Aerial Robotics: Lausanne, Switzerland. This paper presents and overview of the basic and applied research carried out by the Computer Vision Laboratory, Linköping University, in the WITAS UAV Project. This work includes customizing and redesigning vision methods to fit the particular needs and restrictions imposed by the UAV platform, e.g., for low-level vision, motion estimation, navigation, and tracking. It also includes a new learning structure for association of perception-action activations, and a runtime system for implementation and execution of vision algorithms. The paper contains also a brief introduction to the WITAS UAV Project. [67] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2002. CAKE: A computer aided knowledge engineering technique. In Frank van Harmelen, editor, Proceedings of the 15th European Conference on Artificial Intelligence,2002, pages 220–224. IOS Press. Introduction: Logic engineering often involves the development of modeling tools and inference mechanisms (both standard and non-standard) which are targeted for use in practical applications where expressiveness in representation must be traded off for efficiency in use. Some representative examples of such applications would be the structuring and querying of knowledge on the semantic web, or the representation and querying of epistemic states used with softbots, robots or smart devices. In these application areas, declarative representations of knowledge enhance the functionality of such systems and also provide a basis for insuring the pragmatic properties of modularity and incremental composition. In addition, the mechanisms developed should be tractable, but at the same time, expressive enough to represent such aspects as default reasoning, or approximate or incomplete representations of the environments in which the entities in question are embedded or used, be they virtual or actual. [...] [66] Per Andersson, Krzysztof Kuchcinski, Klas Nordberg and Patrick Doherty. 2002. Integrating a computational model and a run time system for image processing on a UAV. In Euromicro Symposium on Digital System Design (DSD), pages 102–109. DOI: 10.1109/DSD.2002.1115357. Recently substantial research has been devoted to Unmanned Aerial Vehicles (UAVs). One of a UAV's most demanding subsystem is vision. The vision subsystem must dynamically combine different algorithms as the UAVs goal and surrounding change. To fully utilize the available hardware, a run time system must be able to vary the quality and the size of regions the algorithms are applied to, as the number of image processing tasks changes. To allow this the run time system and the underlying computational model must be integrated. In this paper we present a computational model suitable for integration with a run time system. The computational model is called Image Processing Data Flow Graph (IP-DFG). IP-DFG has been developed for modeling of complex image processing algorithms. IP-DFG is based on data flow graphs, but has been extended with hierarchy and new rules for token consumption, which makes the computational model more flexible and more suitable for human interaction. In this paper we also show that IP-DFGs are suitable for modelling expressions, including data dependent decisions and iterations, which are common in complex image processing algorithms. 2001 [65] Fredrik Heintz and Patrick Doherty. 2001. Chronicle Recognition in the WITAS UAV Project: A Preliminary Report. In Proceedings of the Swedish AI Society Workshop. This paper describes the chronicle recognition problem and reports its status in the WITAS UAV project. We describe how we use the IxTeT chronicle recognition system to define chronicles (scenarios or situations), like a vehicle passing another vehicle, and how it is incorporated in the WITAS architecture. We also discuss known problems with the current system and possible directions of future research. [64] Patrick Doherty and Jonas Kvarnström. 2001. TALPLANNER - A temporal logic-based planner. The AI Magazine, 22(3):95–102. AAAI Press. TALPLANNER is a forward-chaining planner that utilizes domain-dependent knowledge to control search in the state space generated by action invocation. The domain-dependent control knowledge, background knowledge, plans, and goals are all represented, using,formulas in, a temporal logic called TAL, which has been developed independently as a formalism for specifying agent narratives and reasoning about them. In the Fifth International Artificial Intelligence Planning and Scheduling Conference planning competition, TALPLANNER exhibited impressive performance, winning the Outstanding Performance Award in the Domain-Dependent Planning Competition. In this article, we provide an overview of TALPLANNER. [63] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2001. Computing strongest necessary and weakest sufficient conditions of first-order formulas. In 17th International Joint Conference on Artificial Intelligence,2001, pages 145–151. Morgan Kaufmann Publishers Inc.. ISBN: 1-55860-812-5, 978-1-558-60812-2. A technique is proposed for computing the weakest sufficient (wsc) and strongest necessary (snc) conditions for formulas in an expressive fragment of first-order logic using quantifier elimination techniques. The efficacy of the approach is demonstrated by using the techniques to compute snc's and wsc's for use in agent communication applications, theory approximation and generation of abductive hypotheses. Additionally, we generalize recent results involving the generation of successor state axioms in the propositional situation calculus via snc's to the first-order case. Subsumption results for existing approaches to this problem and a re-interpretation of the concept of forgetting as a process of quantifier elimination are also provided. 2000 [62] Patrick Doherty and Jonas Kvarnström. 2000. TALplanner: A temporal logic based forward chaining planner. Annals of Mathematics and Artificial Intelligence, 30(1-4):119–169. Springer. DOI: 10.1023/A:1016619613658. We present TALplanner, a forward-chaining planner based on the use of domain-dependent search control knowledge represented as formulas in the Temporal Action Logic (TAL). TAL is a narrative based linear metric time logic used for reasoning about action and change in incompletely specified dynamic environments. TAL is used as the formal semantic basis for TALplanner, where a TAL goal narrative with control formulas is input to TALplanner which then generates a TAL narrative that entails the goal and control formulas. The sequential version of TALplanner is presented. The expressivity of plan operators is then extended to deal with an interesting class of resource types. An algorithm for generating concurrent plans, where operators have varying durations and internal state, is also presented. All versions of TALplanner have been implemented. The potential of these techniques is demonstrated by applying TALplanner to a number of standard planning benchmarks in the literature. [61] Patrick Doherty, Witold Lukaszewicz and E. Madalin´ska-Bugaj. 2000. The PMA and relativizing minimal change for action update. Fundamenta Informaticae, 44(1-2):95–131. IOS Press. Recently, a great deal of progress has been made using nonmonotonic temporal logics to formalize reasoning about action and change. In particular, much focus has been placed on the proper representation of non-deterministic actions and the indirect effects of actions. For the latter the use of causal or fluent dependency rule approaches has been dominant. Although much recent effort has also been spent applying the belief revision/update (BR/U) approach to the action and change domain, there has been less progress in dealing with nondeterministic update and indirect effects represented as integrity constraints. We demonstrate that much is to be gained by cross-fertilization between the two paradigms and we show this in the following manner. We first propose a generalization of the PMA, called the modified MPMA which uses intuitions from the TL paradigm to permit representation of nondeterministic update and the use of integrity constraints interpreted as causal or fluent dependency rules. We provide several syntactic characterizations of MPMA, one of which is in terms of a simple temporal logic and provide a representation theorem showing equivalence between the two. In constructing the MPMA, we discovered a syntactic anomaly which we call the redundant atom anomaly that many TL approaches suffer from. We provide a method for avoiding the problem which is equally applicable across paradigms. We also describe a syntactic characterization of MPMA in terms of Dijkstra semantics. We set up a framework for future generalization of the BR/U approach and conclude with a formal comparison of related approaches. [60] Jonas Kvarnström and Patrick Doherty. 2000. Tackling the qualification problem using fluent dependency constraints. Computational intelligence, 16(2):169–209. Blackwell Publishing. DOI: 10.1111/0824-7935.00111. In the area of formal reasoning about action and change, one of the fundamental representation problems is providing concise modular and incremental specifications of action types and world models, where instantiations of action types are invoked by agents such as mobile robots. Provided the preconditions to the action are true, their invocation results in changes to the world model concomitant with the goal-directed behavior of the agent. One particularly difficult class of related problems, collectively called the qualification problem, deals with the need to find a concise incremental and modular means of characterizing the plethora of exceptional conditions that might qualify an action, but generally do not, without having to explicitly enumerate them in the preconditions to an action. We show how fluent dependency constraints together with the use of durational fluents can be used to deal with problems associated with action qualification using a temporal logic for action and change called TAL-Q. We demonstrate the approach using action scenarios that combine solutions to the frame, ramification, and qualification problems in the context of actions with duration, concurrent actions, nondeterministic actions, and the use of both Boolean and non-Boolean fluents. The circumscription policy used for the combined problems is reducible to the first-order case. [59] Jonas Kvarnström, Patrick Doherty and Patrik Haslum. 2000. Extending TALplanner with concurrency and resources. In Proceedings of the 14th European Conference on Artificial Intelligence (ECAI), pages 501–505. In series: Frontiers in Artificial Intelligence and Applications #54. IOS Press. ISBN: 4274903885, 1586030132. Link: http://swepub.kb.se/bib/swepub:oai:DiVA.... We present TALplanner, a forward-chaining planner based on the use of domain-dependent search control knowledge represented as temporal formulas in the Temporal Action Logic (TAL). TAL is a narrative based linear metric time logic used for reasoning about action and change in incompletely specified dynamic environments. TAL is used as the formal semantic basis for TALplanner, where a TAL goal narrative with control formulas is input to TALplanner which then generates a TAL narrative that entails the goal formula. We extend the sequential version of TALplanner, which has previously shown impressive performance on standard benchmarks, in two respects: 1) TALplanner is extended to generate concurrent plans, where operators have varied durations and internal state; and 2) the expressiveness of plan operators is extended for dealing with several different types of resources. The extensions to the planner have been implemented and concurrent planning with resources is demonstrated using an extended logistics benchmark. [58] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2000. Efficient reasoning using the local closed-world assumption. In Proceedings of the 9th International Conference on Artificial Intelligence: Methodology, Systems and Applications (AIMSA), pages 49–58. In series: Lecture Notes in Computer Science #1904. Springer Berlin/Heidelberg. ISBN: 978-3-540-41044-7 (print), 978-3-540-45331-4 (online). DOI: 10.1007/3-540-45331-8_5. We present a sound and complete, tractable inference method for reasoning with localized closed world assumptions (LCWA’s) which can be used in applications where a reasoning or planning agent can not assume complete information about planning or reasoning states. This Open World Assumption is generally necessary in most realistic robotics applications. The inference procedure subsumes that described in Etzioni et al [9], and others. In addition, it provides a great deal more expressivity, permitting limited use of negation and disjunction in the representation of LCWA’s, while still retaining tractability. The ap- proach is based on the use of circumscription and quantifier elimination techniques and inference is viewed as querying a deductive database. Both the preprocessing of the database using circumscription and quan- tifier elimination, and the inference method itself, have polynomial time and space complexity. [57] Patrick Doherty, Gösta Granlund, Krzysztof Kuchcinski, Erik Johan Sandewall, Klas Nordberg, Erik Skarman and Johan Wiklund. 2000. The WITAS unmanned aerial vehicle project. In Werner Horn, editor, Proceedings of the 14th European Conference on Artificial Intelligence (ECAI), pages 747–755. IOS Press. ISBN: 1-58603-013-2, 4-274-90388-5. Link: http://www2.cvl.isy.liu.se/ScOut/Publica... The purpose of this paper is to provide a broad overview of the WITAS Unmanned Aerial Vehicle Project. The WITAS UAV project is an ambitious, long-term basic research project with the goal of developing technologies and functionalities necessary for the successful deployment of a fully autonomous UAV operating over diverse geographical terrain containing road and traffic networks. Theproject is multi-disciplinary in nature, requiring many different research competences, and covering a broad spectrum of basic research issues, many of which relate to current topics in artificial intelligence. A number of topics considered are knowledge representation issues, active vision systems and their integration with deliberative/reactive architectures, helicopter modeling and control, ground operator dialogue systems, actual physical platforms, and a number of simulation techniques. [56] Gösta Granlund, Klas Nordberg, Johan Wiklund, Patrick Doherty, Erik Skarman and Erik Sandewall. 2000. WITAS: An Intelligent Autonomous Aircraft Using Active Vision. In Proceedings of the UAV 2000 International Technical Conference and Exhibition (UAV). Euro UVS. The WITAS Unmanned Aerial Vehicle Project is a long term basic research project located at Linköping University (LIU), Sweden. The project is multi-disciplinary in nature and involves cooperation with different departments at LIU, and a number of other universities in Europe, the USA, and South America. In addition to academic cooperation, the project involves collaboration with a number of private companies supplying products and expertise related to simulation tools and models, and the hardware and sensory platforms used for actual flight experimentation with the UAV. Currently, the project is in its second phase with an intended duration from 2000-2003.This paper will begin with a brief overview of the project, but will focus primarily on the computer vision related issues associated with interpreting the operational environment which consists of traffic and road networks and vehicular patterns associated with these networks. 1999 [55] Patrick Doherty, Jaroslaw Kachniarz and Andrzej Szalas. 1999. Meta-queries on deductive databases. Fundamenta Informaticae, 40(1):17–30. IOS Press. DOI: 10.3233/FI-1999-40102. We introduce the notion of a meta-query on relational databases and a technique which can be used to represent and solve a number of interesting problems from the area of knowledge representation using logic. The technique is based on the use of quantifier elimination and may also be used to query relational databases using a declarative query language called SHQL (Semi-Horn Query Language), introduced in [6]. SHQL is a fragment of classical first-order predicate logic and allows us to define a query without supplying its explicit definition. All SHQL queries to the database can be processed in polynomial time (both on the size of the input query and the size of the database). We demonstrate the use of the technique in problem solving by structuring logical puzzles from the Knights and Knaves domain as SHQL meta-queries on relational databases. We also provide additional examples demonstrating the flexibility of the technique. We conclude with a description of a newly developed software tool, The Logic Engineer, which aids in the description of algorithms using transformation and reduction techniques such as those applied in the meta-querying approach. [54] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1999. Declarative PTIME queries for relational databases using quantifier elimination. Journal of logic and computation (Print), 9(5):737–758. Oxford University Press. DOI: 10.1093/logcom/9.5.737. In this paper, we consider the problem of expressing and computing queries on relational deductive databases in a purely declarative query language, called SHQL (Semi-Horn Query Language). Assuming the relational databases in question are ordered, we show that all SHQL queries are computable in PTIME (polynomial time) and the whole class of PTIME queries is expressible in SHQL. Although similar results have been proven for fixpoint languages and extensions to datalog, the claim is that SHQL has the advantage of being purely declarative, where the negation operator is interpreted as classical negation, mixed quantifiers may be used and a query is simply a restricted first-order theory not limited by the rule-based syntactic restrictions associated with logic programs in general. We describe the PTIME algorithm used to compute queries in SHQL which is based in part on quantifier elimination techniques and also consider extending the method to incomplete relational databases using intuitions related to circumscription techniques. [53] Patrick Doherty, Witold Lukaszewicz and E. Madalin´ska-Bugaj. 1999. Computing MPMA updates using dijkstra's semantics. In 12th International Symposium on Methodologies for Intelligent Systems,1999. Springer. [52] Patrick Doherty and Jonas Kvarnström. 1999. TALplanner: An empirical investigation of a temporal logic-based forward chaining planner. In Clare Dixon, Michael Fisher, editors, 6th International Workshop on Temporal Representation and Reasoning (TIME-99). IEEE Computer Society. ISBN: 0-7695-0173-7. We present a new forward chaining planner, TALplanner, based on ideas developed by Bacchus and Kabanza, where domain-dependent search control knowledge represented as temporal formulas is used to effectively control forward chaining. Instead of using a linear modal tense logic as with Bacchus and Kabanza, we use TAL, a narrative-based linear temporal logic used for reasoning about action and change in incompletely specified dynamic environments. Two versions of TALplanner are considered, TALplan/modal which is based on the use of emulated modal formulas and a progression algorithm, and TALplan/non-modal which uses neither modal formulas nor a progression algorithm. For both versions of TALplanner and for all tested domains, TALplanner is shown to be considerably faster and requires less memory. The TAL versions also permit the representation of durative actions with internal state. [51] John-Jules Meyer and Patrick Doherty. 1999. Preferential action semantics (preliminary report). In Formal Models of Agents: ESPRIT Project Modelage Final Workshop Selected Papers, pages 187–201. In series: Lecture Notes in Artificial Intelligence #1760. Springer. ISBN: 3-540-67027-0. DOI: 10.1007/3-540-46581-2_13. Note: Preliminary report In this paper, we propose a new way of considering reasoning about action and change. Rather than placing a preferential structure onto the models of logical theories, we place such a structure directly on the semantics of the actions involved. In this way, we obtain a preferential semantics of actions by means of which we can not only deal with several of the traditional problems in this area such as the frame and ramification problems, but can generalize these solutions to a context which includes both nondeterministic and concurrent actions. In fact, the net result is an integration of semantical and verificational techniques from the paradigm of imperative and concurrent programs in particular, as known from traditional programming, with the AI perspective. In this paper, the main focus is on semantical (i.e. model theoretical) issues rather than providing a logical calculus, which would be the next step in the endeavor. 1998 [50] Patrick Doherty and Joakim Gustafsson. 1998. Delayed effects of actions = direct effects + causal rules. Technical Report. In series: Linköping Electronic Articles in Computer and Information Science #98-001. Linköping University Electronic Press. Link: http://www.ep.liu.se/ea/cis/1998/001/ We propose an approach to modeling delayed effects of actions which is based on the use of causal constraints and their interaction with the direct effects of actions. The approach extends previous work with a causal approach used to deal with the ramification problem. We show the similarity between solutions to the modeling of indirect effects and delayed effects of actions by example. The base logic PMON+ is a temporal logic for reasoning about action and change and uses circumscription. It is shown that the extension for delayed effects of actions retains the first-order reducibility property shown previously for successfully dealing with the frame and ramification problems for a large class of action scenarios. We also consider the “causal qualification” problem, \"natural death\" of fluents and causal lag, each of which is closely related to the use of delayed effects. [49] Patrick Doherty, Joakim Gustafsson, Lars Karlsson and Jonas Kvarnström. 1998. (TAL) temporal action logics: Language specification and tutorial. Electronic Transactions on Artifical Intelligence, 2(3-4):273–306. Link: http://www.ep.liu.se/ej/etai/1998/009/ The purpose of this article is to provide a uniform, lightweight language specication and tutorial for a class of temporal logics for reasoning about action and change that has been developed by our group during the period 1994-1998. The class of logics are collected under the name TAL, an acronym for Temporal Action Logics. TAL has its origins and inspiration in the work with Features and Fluents (FF) by Sandewall, but has diverged from the methodology and approach through the years. We first discuss distinctions and compatibility with FF, move on to the lightweight language specication, and then present a tutorial in terms of an excursion through the different parts of a relatively complex narrative defined using TAL. We conclude with an annotated list of published work from our group. The article tries to strike a reasonable balance between detail and readability, making a number of simplications regarding narrative syntax and translation to a base logical language. Full details are available in numerous technical reports and articles which are listed in the final section of this article. [48] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1998. General domain circumscription and its effective reductions. Fundamenta Informaticae, 36(1):23–55. IOS Press. DOI: 10.3233/FI-1998-3612. We first define general domain circumscription (GDC) and provide it with a semantics. GDC subsumes existing domain circumscription proposals in that it allows varying of arbitrary predicates, functions, or constants, to maximize the minimization of the domain of a theory. We then show that for the class of semi-universal theories without function symbols, that the domain circumscription of such theories can be constructively reduced to logically equivalent first-order theories by using an extension of the DLS algorithm, previously proposed by the authors for reducing second-order formulas. We also show that for a certain class of domain circumscribed theories, that any arbitrary second-order circumscription policy applied to these theories is guaranteed to be reducible to a logically equivalent first-order theory. In the case of semi-universal theories with functions and arbitrary theories which are not separated, we provide additional results, which although not guaranteed to provide reductions in all cases, do provide reductions in some cases. These results are based on the use of fixpoint reductions. [47] Lars Karlsson, Joakim Gustafsson and Patrick Doherty. 1998. Delayed effects of actions. In Proceedings of the 13th European Conference on Artificial Intelligence (ECAI), pages 542–546. John Wiley & Sons. ISBN: 978-0471984313. [46] Patrick Doherty, Witold Lukaszewicz and Ewa Madalinska-Bugaj. 1998. The PMA and relativizing change for action update. In Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 258–269. Morgan Kaufmann Publishers. Using intuitions from the temporal reasoning community, we provide a generalization of the PMA, called the modified PMA (MPMA), which permits the representation of disjunctive updates and the use of integrity constraints interpreted as causal constraints. In addition, we provide a number of syntactic characterizations of the MPMA, one of which is constructed by mapping an MPMA update of a knowledge base into a temporal narrative in a simple temporal logic (STL). The resulting representation theorem provides a basis for computing entailments of the MPMA and could serve as a basis for further generalization of the belief update approach for reasoning about action and change. [45] Patrick Doherty and Jonas Kvarnström. 1998. Tackling the qualification problem using fluent dependency constraints. In Lina Khatib, Robert Morris, editors, Proceedings of the 5th International Workshop on Temporal Representation and Reasoning (TIME-98). IEEE Computer Society. ISBN: 0-8186-8473-9. Note: Preliminary report The use of causal rules or fluent dependency constraints has proven to provide a versatile means of dealing with the ramification problem. In this paper we show how fluent dependency constraints together with the use of durational fluents can be used to deal with problems associated with action qualification. We provide both a \emph{weak} and \emph{strong} form of qualification and demonstrate the approach using an action scenario which combines solutions to the frame, ramification and qualification problems in the context of actions with duration, concurrent actions, non-deterministic actions and the use of both boolean and non-boolean fluents. The circumscription policy used for the combined problems is reducible to the 1st-order case. In addition, we demonstrate the use of a research tool VITAL, for querying and visualizing action scenarios. 1997 [44] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1997. Computing circumscription revisited: A reduction algorithm. Journal of automated reasoning, 18(3):297–336. Kluwer Academic Publishers. DOI: 10.1023/A:1005722130532. In recent years, a great deal of attention has been devoted to logics of common-sense reasoning. Among the candidates proposed, circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic reasoning, but difficult to apply in practice. The major reason for this is the second-order nature of circumscription axioms and the difficulty in finding proper substitutions of predicate expressions for predicate variables. One solution to this problem is to compile, where possible, second-order formulas into equivalent first-order formulas. Although some progress has been made using this approach, the results are not as strong as one might desire and they are isolated in nature. In this article, we provide a general method that can be used in an algorithmic manner to reduce certain circumscription axioms to first-order formulas. The algorithm takes as input an arbitrary second-order formula and either returns as output an equivalent first-order formula, or terminates with failure. The class of second-order formulas, and analogously the class of circumscriptive theories that can be reduced, provably subsumes those covered by existing results. We demonstrate the generality of the algorithm using circumscriptive theories with mixed quantifiers (some involving Skolemization), variable constants, nonseparated formulas, and formulas with n-ary predicate variables. In addition, we analyze the strength of the algorithm, compare it with existing approaches, and provide formal subsumption results. 1996 [43] Patrick Doherty. 1996. PMON+: A fluent logic for action and change - formal specification, version 1.0. Technical Report. In series: LITH-IDA-R #33. Department of Computer and Information Science, Linköping University. This report describes the current state of work with PMON, a logic for reasoning about action and change, and its extensions. PMON has been assessed correct for the K-IA class using Sandewall's Features and Fluents framework which provides tools for assessing the correctness of logics of action and change. A syntactic characterization of PMON has previously been provided in terms of a circumscription axiom which is shown to be reducible to a first-order formula. This report introduces a number of new extensions which are also reducible and deal with ramification. The report is intended to provide a formal specification for the PMON family of logics and the surface language L(SD) used to represent action scenario descriptions. It should be considered a working draft. The title of the report has a version number because both the languages and logics used are continually evolving. Since this document is intended as a formal specification which is used by our group as a reference for research and implementation, it is understandably brief as regards intuitions and applications of the languages and logics defined. We do provide a set of benchmarks and comments concerning these which can serve as a means of comparing this formalism with others. The set of benchmarks is not complete and is only intended to provide representative examples of the expressivity and use of this particular family of logics. We describe its features and limitations in other publications by our group which can normally be found at \"http://www.ida.liu.se/labs/kplab/\". [42] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996. Declarative ptime queries to relational databases. Technical Report. In series: LITH-IDA-R #34. Department of Computer and Information Science, Linköping University. [41] John-Jules Meyer and Patrick Doherty. 1996. Preferential action semantics, preliminary report. Technical Report. In series: LITH-IDA-R #??. Department of Computer and Information Science, Linköping University. In this paper, we propose a new way of considering reasoning about action and change. Rather than placing a preferential structure onto the models of logical theories, we place such a structure directly on the semantics of the actions involved. In this way, we obtain a preferential semantics of actions by means of which we can not only deal with several of the traditional problems in this area such as the frame and ramification problems, but can generalize these solutions to a context which includes both nondeterministic and concurrent actions. In fact, the net result is an integration of semantical and verificational techniques from the paradigm of imperative and concurrent programs in particular, as known from traditional programming, with the AI perspective. In this paper, the main focus is on semantical (i.e. model theoretical) issues rather than providing a logical calculus, which would be the next step in the endeavor. [40] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996. General domain circumscription and its first-order reduction. Technical Report. In series: LITH-IDA-R #1. Department of Computer and Information Science, Linköping University. [39] Patrick Doherty and Witold Lukaszewicz. 1996. A study in modal embeddings of NML3. In Patrick Doherty, editor, Partiality, Modality, and Nonmonotonicity, Studies in Logic, Language and Information., pages 145–168. CSLI Publications. ISBN: 1-57586-031-7 (inb.), 1-57586-030-9 (hft.). [38] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996. A reduction result for circumscribed semi-horn formulas. Fundamenta Informaticae, 28(3,4):261–272. IOS Press. DOI: 10.3233/FI-1996-283404. Circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic and commonsense reasoning, but difficult to apply in practice due to the use of second-order formulas. One proposal for dealing with the computational problems is to identify classes of first-order formulas whose circumscription can be shown to be equivalent to a first-order formula. In previous work, we presented an algorithm which reduces certain classes of second-order circumscription axioms to logically equivalent first-order formulas. The basis for the algorithm is an elimination lemma due to Ackermann. In this paper, we capitalize on the use of a generalization of Ackermann's Lemma in order to deal with a subclass of universal formulas called semi-Horn formulas. Our results subsume previous results by Kolaitis and Papadimitriou regarding a characterization of circumscribed definite logic programs which are first-order expressible. The method for distinguishing which formulas are reducible is based on a boundedness criterion. The approach we use is to first reduce a circumscribed semi-Horn formula to a fixpoint formula which is reducible if the formula is bounded, otherwise not. In addition to a number of other extensions, we also present a fixpoint calculus which is shown to be sound and complete for bounded fixpoint formulas. [37] Joakim Gustafsson and Patrick Doherty. 1996. Embracing occlusion in specifying the indirect effects of actions. In Luigia Carlucci Aiello, Jon Doyle, Stuart C. Shapiro, editors, Proceedings of the 5th International Conference on Principles of Knowledge Representation and Reasoning, pages 87–98. Morgan Kaufmann Publishers. ISBN: 1-55860-421-9. In this paper, we extend PMON, a logic for reasoning about action and change, with causal rules which are used to specify the indirect effects of actions The extension, called PMON(RCs), has the advantage of using explicit time, includes actions with durations, nondeterministic actions, allows partial specification of the timing and order of actions and has been assessed correct for at least the K-IA class of action scenarios within the Features and Fluents framework Most importantly, the circumscription policy used is easily shown to be reducible to the firstorder case which insures that standard theorem proving techniques and their optimizations may be used to compute entailment In addition, we show how the occlusion concept previously used to deal with duration and nondeterministic actions proves to be equally versatile in representing causal constraints and delayed effects of actions We also discuss related work and consider the strong correspondence between our work and recent work by Lin, who uses a Cause predicate to specify indirect effects similar to our use of Occlude in PMON, and a minimization policy related to that used in PMON. [36] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996. Explaining explanation closure. In Zbigniew W. Ras, Maciek Michalewicz, editors, Proceedings of the 9th International Symposium on Methodologies for Intelligent Systems,1996, pages 521–530. In series: Lecture Notes in Computer Science #1079. Springer Berlin/Heidelberg. ISBN: 3-540-61286-6. DOI: 10.1007/3-540-61286-6_176. Recently, Haas, Schubert, and Reiter, have developed an alternative approach to the frame problem which is based on the idea of using explanation closure axioms. The claim is that there is a monotonic solution for characterizing nonchange in serial worlds with fully specified actions, where one can have both a succinct representation of frame axioms and an effective proof theory for the characterization. In the paper, we propose a circumscriptive version of explanation closure, PMON, that has an effective proof theory and works for both context dependent and nondeterministic actions. The approach retains representational succinctness and a large degree of elaboration tolerance, since the process of generating closure axioms is fully automated and is of no concern to the knowledge engineer. In addition, we argue that the monotonic/nonmonotonic dichotomy proposed by others is not as sharp as previously claimed and is not fully justified. [35] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996. General domain circumscription and its first-order reduction. In Dov Gabbay, Hans Olbach, editors, Proceedings of the 1st International Conference on Formal and Applied Practical Reasoning (FAPR), pages 93–109. In series: Lecture Notes in Computer Science #1085. Springer Berlin/Heidelberg. ISBN: 978-3-540-61313-8. DOI: 10.1007/3-540-61313-7_65. We first define general domain circumscription (GDC) and provide it with a semantics. GDC subsumes existing domain circumscription proposals in that it allows varying of arbitrary predicates, functions, or constants, to maximize the minimization of the domain of a theory We then show that for the class of semi-universal theories without function symbols, that the domain circumscription of such theories can be constructively reduced to logically equivalent first-order theories by using an extension of the DLS algorithm, previously proposed by the authors for reducing second-order formulas. We also isolate a class of domain circumscribed theories, such that any arbitrary second-order circumscription policy applied to these theories is guaranteed to be reducible to a logically equivalent first-order theory. In the case of semi-universal theories with functions and arbitrary theories which are not separated, we provide additional results, which although not guaranteed to provide reductions in all cases, do provide reductions in some cases. These results are based on the use of fixpoint reductions. 1995 [34] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1995. A characterization result for circumscribed normal logic programs. Revised version accepted for publication: Special issue of honor of H. Rasiowa, Fundamenta Informaticae. Technical Report. In series: LITH-IDA-R #20. Department of Computer and Information Science, Linköping University. [33] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1995. Computing circumscription revisited. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI), pages 1502–1508. ISBN: 978-1558603639. Note: Volume 2. Preliminary report [32] Patrick Doherty and P. Peppas. 1995. A comparison between two approaches to ramification: PMON(R) and AR0. In 8th Australian Joint Conference on Artificial Intelligence,1995. Note: World Scientific 1994 [31] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1994. Computing circumscription revisited: A reduction algorithm. Technical Report. In series: LITH-IDA-R #94-42. Department of Computer and Information Science, Linköping University. In recent years, a great deal of attention has been devoted to logics of \"commonsense\" reasoning. Among the candidates proposed, circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic reasoning, but difficult to apply in practice. The major reason for this is the nd-order nature of circumscription axioms and the difficulty in finding proper substitutions of predicate expressions for predicate variables. One solution to this problem is to compile, where possible, nd-order formulas into equivalent 1st-order formulas. Although some progress has been made using this approach, the results are not as strong as one might desire and they are isolated in nature. In this article, we provide a general method which can be used in an algorithmic manner to reduce circumscription axioms to 1st-order formulas. The algorithm takes as input an arbitrary 2nd-order formula and either returns as output an equivalent 1st-order formula, or terminates with failure. The class of 2nd-order formulas, and analogously the class of circumscriptive theories which can be reduced, provably subsumes those covered by existing results. We demonstrate the generality of the algorithm using circumscriptive theories with mixed quantifiers (some involving Skolemization), variable constants, non-separated formulas, and formulas with n-ary predicate variables. In addition, we analyze the strength of the algorithm and compare it with existing approaches providing formal subsumption results. [30] Patrick Doherty. 1994. Notes on PMON circumscription. Technical Report. In series: LITH-IDA-R #43. Department of Computer and Information Science, Linköping University. [29] Patrick Doherty and Witold Lukaszewicz. 1994. Circumscribing features and fluents. A fluent logic for reasoning about action and change. In 8th International Symposium on Methodologies for Intelligent Systems,1994. Springer Verlag. [28] Patrick Doherty and Witold Lukaszewicz. 1994. Circumscribing features and fluents. In Dov M. Gabbay and Hans Jürgen Ohlbach, editors, Temporal Logic: First International Conference, ICTL'94 Bonn, Germany, July 11–14, 1994 Proceedings, pages 82–100. In series: Lecture Notes in Computer Science #827. Springer Berlin/Heidelberg. ISBN: 3-540-58241-X (Berlin), 0-387-58241-X (New York). DOI: 10.1007/BFb0013982. Sandewall has recently proposed a systematic approach to the representation of knowledge about dynamical systems that includes a general framework in which to assess the range of applicability of existing and new logics for action and change and to provide a means of studying whether and in what sense the logics of action and change are relevant for intelligent agents. As part of the framework, a number of logics of preferential entailment are introduced and assessed for particular classes of action scenario descriptions. This paper provides syntactic characterizations of several of these relations of preferential entailment in terms of standard FOPC and circumscription axioms. The intent is to simplify the process of comparison with existing formalisms which use more traditional techniques and to provide a basis for studying the feasibility of compiling particular classes of problems into logic programs. [27] Patrick Doherty. 1994. Reasoning about action and change using occlusion. In 11th European Conference on Artificial Intelligence,1994. John Wiley and Sons. 1993 [26] Patrick Doherty and Dimiter Driankov. 1993. Nonmonotonicity, fuzziness, and multi-values. In R. Lowen and M. Roubens, editors, Fuzzy Logic: State of the Art. Series D: System Theory, Knowledge Engineering and Problem Solving.. In series: Volume 12 #12. Kluwer Academic Publishers. ISBN: 0792323246, 9780792323242. [25] Patrick Doherty, Dimiter Driankov and Hans Hellendoorn. 1993. Fuzzy if-then-unless rules and their implementation. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 1(2):167–182. World Scientific. DOI: 10.1142/S0218488593000097. We consider the possibility of generalizing the notion of a fuzzy If-Then rule to take into account its context dependent nature. We interpret fuzzy rules as modeling a forward directed causal relationship between the antecedent and the conclusion, which applies in most contexts, but on occasion breaks down in exceptional contexts. The default nature of the rule is modeled by augmenting the original If-Then rule with an exception part. We then consider the proper semantic correlate to such an addition and propose a ternary relation which satisfies a number of intuitive constraints described in terms of a number of inference rules. In the rest of the paper, we consider implementational issues arising from the unless extension and propose the use of reason maintenance systems, in particular TMS's, where a fuzzy If-Then-Unless rule is encoded into a dependency net. We verify that the net satisfies the constraints stated in the inference schemes and conclude with a discussion concerning the integration of qualitative IN-OUT labelings of the TMS with quantitative degree of membership labelings for the variables in question. 1992 [24] Patrick Doherty and Witold Lukaszewicz. 1992. FONML3 - A first-order non-monotonic logic with explicit defaults. Technical Report. In series: LITH-IDA-R #20. Department of Computer and Information Science, Linköping University. [23] Patrick Doherty, Dimiter Driankov and H. Hellendoorn. 1992. Fuzzy if-then-unless rules and their implementation. Technical Report. In series: LITH-IDA-R #21. Department of Computer and Information Science, Linköping University. [22] Patrick Doherty, Dimiter Driankov and A. Tsoukias. 1992. Partiality, para-consistency and preference modeling: Preliminary version. Technical Report. In series: LITH-IDA-R #18. Department of Computer and Information Systems, Linköping University. [21] Patrick Doherty. 1992. A constraint-based approach to proof procedures for multi-valued logics. Technical Report. In series: LITH-IDA-R #2. Department of Computer and Information Science, Linköping university, Linköping, Sweden. [20] Patrick Doherty and Witold Lukaszewicz. 1992. Distinguishing between facts and default assumptions. In W. van der Hoek, editor, Non-Monotonic Reasoning and Partial Semantics. Ellis Horwood Workshops.. Ellis Horwood Ltd.. ISBN: 0136251463, 9780136251460. [19] Dimiter Driankov and Patrick Doherty. 1992. A non-monotonic fuzzy logic. In Lotfi A. Zadeh, Janusz Kacprzyk, editors, Fuzzy Logic for the Management of Uncertainty, pages 171–190. John Wiley & Sons. ISBN: 0-471-54799-9. [18] Patrick Doherty and Witold Lukaszewicz. 1992. NML-3 - A non-monotonic logic with explicit defaults. Journal of applied non-classical logics, 2(1):9–48. Éditions Hermès-Lavoisier. [17] Patrick Doherty and Witold Lukaszewicz. 1992. Defaults as first-class citizens. In Proceedings of the 22nd International Symposium on Multiple-Valued Logic (SMVL), pages 146–154. In series: Proceedings of the International Symposium on Multiple Valued Logic #??. IEEE Computer Society. ISBN: 0-8186-2680-1. A nonmonotonic logic with explicit defaults, NML3, is presented. It is characterized by the following features: (1) the use of the strong Kleene three-valued logic as a basis; (2) the addition of an explicit default operator which enables distinguishing tentative conclusions from ordinary conclusions in the object language; and (3) the use of the idea of preferential entailment to generate nonmonotonic behavior. The central feature of the formalism, the use of an explicit default operator with a model-theoretic semantics based on the notion of a partial interpretation, distinguishes NML3 from most previous formalisms. By capitalizing on the distinction between tentative and ordinary conclusions, NML3 provides increased expressibility in comparison to many of the standard nonmonotonic formalisms and greater flexibility in the representation of subtle aspects of default reasoning. This is shown through examples. [16] Patrick Doherty and Witold Lukaszewicz. 1992. FONML3 - A first-order non-monotonic logic with explicit defaults. In European Conference on Artificial Intelligence, ECAI-92,1992. John Wiley and Sons. [15] Patrick Doherty, Dimiter Driankov and H. Hellendoorn. 1992. Fuzzy if-then-unless rules and their implementation. In International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU92,1992. Springer. [14] Patrick Doherty, Dimiter Driankov and A. Tsoukias. 1992. Partial logics and partial preferences. In International Conference on Economics/Management and Information Technology,1992. 1991 [13] Patrick Doherty and Witold Lukaszewicz. 1991. NML3 - A non-monotonic logic with explicit defaults. Technical Report. In series: Användarrapport #13. Department of Computer and Information Science, Linköping University. [12] Patrick Doherty and Dimiter Driankov. 1991. A non-monotonic fuzzy logic. In International Fuzzy Systems Association, Fourth World Congress,1991. [11] Patrick Doherty. 1991. NML3: a non-monotonic formalism with explicit defaults. PhD Thesis. In series: Linköping Studies in Science and Technology. Dissertations #258. Linköpings tekniska högskola. 290 pages. ISBN: 91-7870-816-8. The thesis is a study of a particular approach to defeasible reasoning based on the notion of an information state consisting of a set of partial interpretations constrained by an information ordering. The formalism proposed, called NML3, is a non-monotonic logic with explicit defaults and is characterized by the following features: (1) The use of the strong Kleene three-valued logic as a basis. (2) The addition of an explicit default operator which enables distinguishing tentative conclusions from ordinary conclusions in the object language. (3) The use of the technique of preferential entailment to generate non-monotonic behavior. The central feature of the formalism, the use of an explicit default operator with a model theoretic semantics based on the notion of a partial interpretation, distinguishes NML3 from the existing formalisms. By capitalizing on the distinction between tentative and ordinary conclusions, NML3 provides increased expressibility in comparison to many of the standard non-monotonic formalisms and greater flexibility in the representation of subtle aspects of default reasoning.In addition to NML3, a novel extension of the tableau-based proof technique is presented where a signed formula is tagged with a set of truth values rather than a single truth value. This is useful if the tableau-based proof technique is to be generalized to apply to the class of multi-valued logics. A refutation proof procedure may then be used to check logical consequence for the base logic used in NML3 and to provide a decision procedure for the propositional case of NML3.A survey of a number of non-standard logics used in knowledge representation is also provided. Various formalisms are analyzed in terms of persistence properties of formulas and their use of information structures. [10] Patrick Doherty. 1991. A constraint-based approach to proof procedures for multi-valued logics. In Proceedings of the 1st World Conference on Fundamentals of Artificial Intelligence (WOCFAI). Springer. 1990 [9] Patrick Doherty. 1990. A three-valued approach to non-monotonic reasoning. Licentiate Thesis. In series: Linköping Studies in Science and Technology. Thesis #230. Linköping University. 117 pages. ISBN: 91-7870-672-6. The subject of this thesis is the formalization of a type of non-monotonic reasoning using a three-valued logic based on the strong definitions of Kleene. Non-monotonic reasoning is the rule rather than the exception when agents, human or machine, must act where information about the environment is uncertain or incomplete. Information about the environment is subject to change due to external causes, or may simply become outdated. This implies that inferences previously made may no longer hold and in turn must be retracted along with the revision of other information dependent on the retractions. This is the variety of reasoning we would like to find formal models for.We start by extending Kleene-s three-valued logic with an \"external negation\" connective where ~ a is true when a is false or unknown. In addition, a default operator D is added where D a is interpreted as \"a is true by default. The addition of the default operator increases the expressivity of the language, where statements such as \"a is not a default\" are directly representable. The logic has an intuitive model theoretic semantics without any appeal to the use of a fixpoint semantics for the default operator. The semantics is based on the notion of preferential entailment, where a set of sentences G preferentially entails a sentence a, if and only if a preferred set of the models of G are models of a. We also show that one version of the logic belongs to the class of cumulative non-monotonic formalisms which are a subject of current interest.A decision procedure for the propositional case, based on the semantic tableaux proof method is described and serves as a basis for a QA-system where it can be determined if a sentence a is preferentially entailed by a set of premises G. The procedure is implemented. [8] Patrick Doherty. 1990. NM3 - A three-valued non-monotonic formalism. Preliminary report. Technical Report. In series: LITH-IDA-R #44. Department of Computer and Information Science, Linköping University. [7] Patrick Doherty. 1990. A correspondence between inheritance hierarchies and a logic of preferential entailment. Technical Report. In series: LITH-IDA-R #??. Department of Computer and Information Science, Linköping University. [6] Patrick Doherty. 1990. NME - A three-valued non-monotonic formalism. In Proceedings of the 5th International Symposium on Methodologies for Intelligent Systems (ISMIS). Note: Preliminary report [5] Patrick Doherty. 1990. NM3 - A three-valued cumulative non-monotonic formalism. In Jan van Eijck, editor, Logics in AI, European Workshop (JELIA), pages 196–211. In series: Lecture Notes in Artificial Intelligence #478. Springer Berlin/Heidelberg. ISBN: 978-3-540-53686-4. DOI: 10.1007/BFb0018442. In this paper, we propose a formalization of non-monotonic reasoning using a three-valued logic based on the strong definitions of Kleene. We start by extending Kleene's three-valued logic with an \"external negation\" connective where ~ alpha is true when alpha is false or unknown. In addition, a default operator D is added where D alpha is interpreted as \"alpha is true by default\". The addition of the default operator increases the expressivity of the language, where statements such as \"alpha is not a default\" are directly representable. The logic has an intuitive model theoretic semantics without any appeal to the use of a fixpoint semantics for the default operator. The semantics is based on the notion of preferential entailment, where a set of sentences Gamma preferentially entails a sentence alpha, if and only if a preferred set of the models of Gamma are models of alpha. We also show that the logic belongs to the class of cumulative non-monotonic formalisms which are a subject of current interest. 1989 [4] Patrick Doherty. 1989. A correspondence between inheritance hierarchies and a logic of preferential entailment. In M. L. Emrich, M. S. Pfeifer, M. Hadzikadic, and Z. W. Ras, editors, Proceedings of the 4th International Symposium on Methodologies for Intelligent Systems (ISMIS). University of North Carolina Press. [3] Patrick Doherty. 1989. A semantics for inheritance hierarchies with exceptions using a logic of preferential entailment. In Proceedings of the 2nd Scandinavian Conference on Artificial Intelligence (SCAI). IOS Press. 1985 [2] Patrick Doherty. 1985. A rule interpreter for an emycin-like expert system tool. Technical Report. In series: Aslab Memo #85-05. Linköpings tekniska högskola. 0 [1] Håkan Warnquist, Jonas Kvarnström and Patrick Doherty. 0. A Modeling Framework for Troubleshooting Automotive Systems. Manuscript (preprint). This paper presents a novel framework for modeling the troubleshooting process for automotive systems such as trucks and buses. We describe how a diagnostic model of the troubleshooting process can be created using event-driven nonstationary dynamic Bayesian networks.Exact inference in such a model is in general not practically possible. Therefore we evaluate different approximate methods for inference based on the Boyen-Koller algorithm. We identify relevant model classes that have particular structure such that inference can be made with linear time complexity using a novel inference algorithm called the Quickscore Variant. We show how the algorithm can be applied for inference when only a single fault is assumed and when multiple faults are possible. We also show another inference method that can be used when multiple faults are possible but a single fault is most likely.We also show how models created using expert knowledge can be tuned using statistical data. The proposed learning mechanism can use data that is collected from a heterogeneous fleet of modular vehicles that can consist of different components.The proposed framework is evaluated both theoretically and experimentally on an application example of a fuel injection system.