# Conference and Workshop Publications

 Hide abstracts BibTeX entries 2014 [300] Dali Sun, Alexander Kleiner and Bernhard Nebel. 2014. Behavior-based Multi-Robot Collision Avoidance. In Robotics and Automation (ICRA), 2014. IEEE. Note: Accepted for publication Autonomous robot teams that simultaneously dis- patch transportation tasks are playing a more and more impor- tant role in the industry. In this paper we consider the multi- robot motion planning problem in large robot teams and present a decoupled approach by combining decentralized path planning methods and swarm technologies. Instead of a central coordi- nation, a proper behavior which is directly selected according to the context is used by the robot to keep cooperating with others and to resolve path collisions. We show experimentally that the quality of solutions and the scalability of our method are significantly better than those of conventional decoupled path planning methods. Furthermore, compared to conventional swarm approaches, our method can be widely applied in large- scale environments. [299] 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). Note: Accepted for Publication. 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. [298] 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. [297] Fredrik Heintz and Inger Erlander Klein. 2014. The Design of Sweden's First 5-year Computer Science and Software Engineering Program. In Proceedings of the 45th ACM Technical Symposium on Computer Science Education (SIGCSE 2014). 2013 [296] 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. [295] Fredrik Heintz and Inger Erlander Klein. 2013. Civilingenjör i Mjukvaruteknik vid Linköpings universitet: mål, design och erfarenheter. In S. Vikström, R. Andersson, F. Georgsson, S. Gunnarsson, J. Malmqvist, S. Pålsson och D. Raudberget, editors, Proceedings of 4:de Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng). In series: UMINF #13:21. Hösten 2013 startade Linköpings universitet den första civilingenjörsutbildningen i Mjukvaruteknik. Utbildningens mål är att bland annat att ge ett helhetsperspektiv på modern storskalig mjukvaruutveckling, ge en gedigen grund i datavetenskap och computational thinking samt främja entreprenörskap och innovation. Studenternas gensvar har varit över förväntan med över 600 sökande till de 30 platserna varav 134 förstahandssökande. Här presenterar vi programmets vision, mål, designprinciper samt det färdiga programmet. En viktig förebild är ACM/IEEE Computer Science Curricula som precis kommit i en ny uppdaterad version. Tre pedagogiska idéer vi har följt är (1) att använda projektkurser för att integrera teori och praktik samt ge erfarenhet i den vanligaste arbetsformen i näringslivet; (2) att undervisa i flera olika programspråk och flera olika programutvecklingsmetodiker för att ge en plattform att ta till sig det senaste på området; och (3) att införa en programsammanhållande kurs i ingenjörsprofessionalism i årskurs 1–3 som ger studenterna verktyg att reflektera över sitt eget lärande, att jobba i näringslivet samt sin professionella yrkesroll. Artikeln avslutas med en diskussion om viktiga aspekter som computational thinking och ACM/IEEE CS Curricula. [294] Fredrik Heintz and Tommy Färnqvist. 2013. Återkoppling genom automaträttning. In Proceedings of 4:de Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng). Vi har undersökt olika former av återkoppling genom automaträttning i en kurs i datastrukturer och algoritmer. 2011 undersökte vi effekterna av tävlingsliknande moment som också använder automaträttning. 2012 införde vi automaträttning av laborationerna. Vi undersökte då hur återkoppling genom automaträttning påverkar studenternasarbetssätt, prestationsgrad och relation till den examinerande personalen. Genom automaträttning får studenterna omedelbar återkoppling om deras program är tillräckligt snabbt och ger rätt svar på testdata. När programmet är korrekt och resurseffektivt kontrollerar kursassistenterna att programmet även uppfyller andra krav som att vara välskrivet och välstrukturerat. Efter kursen undersökte vi studenternas inställning till och upplevelse av automaträttning genom en enkät. Resultaten är att studenterna är positiva till automaträttning (80% av alla som svarade) och att den påverkade studenternas sätt att arbeta huvudsakligen positivt. Till exempel svarade 50% att de ansträngde sig hårdare tack vare automaträttningen. Dessutom blir rättningen mer objektiv då den görs på exakt samma sätt för alla. Vår slutsats är att återkoppling genom automaträttning ger positiva effekter och upplevs som positiv av studenterna. [293] Robin Murphy and Alexander Kleiner. 2013. A Community-Driven Roadmap for the Adoption of Safety Security and Rescue Robots. In . IEEE conference proceedings. Note: Accepted for Publication. The IEEE Safety, Security, and Rescue Robotics community has created a roadmap for producing unmanned systems that could be adopted by the Public Safety sector within 10 years, given appropriate R&D investment especially in human-robot interaction and perception. The five applications expected to be of highest value to the Public Safety community, highest value first, are: assisting with routine inspection of the critical infrastructure, “chronic emergencies” such as firefighting, hazardous material spills, port inspection, and damage estimation after a disaster. The technical feasibility of the applications were ranked, with the most attractive scenario, infrastructure inspection, rated as the second easiest scenario; this suggests the maturity of robotics technology is beginning to match stakeholder needs. Each of the five applications were discussed in terms of the six broad enabling technology areas specified in the current National Robotics Initiative Roadmap (perception, human-robot interaction, mechanisms, modeling and simulation, control and planning, and testing and evaluation) and nine specific capabilities identified by the community as being essential to commercialization (communication, alerting, localization, fault tolerance, mapping, manpower needs, plug and play capabilities, multiple users, and multiple robots). The community believes that perception and human-robot interaction are the two biggest barriers to adoption, and require more research, given that their low technical maturity (3rd and 6th rank respectively). However, each of the specific capabilities needed for commercialization are being addressed by current research and could be achieved within 10 years with sustained funding. [292] Christian Dornhege, Alexander Kleiner and Andreas Kolling. 2013. Coverage Search in 3D. In . Note: Accepted for Publication. Searching with a sensor for objects and to observe parts of a known environment efficiently is a fundamental prob- lem in many real-world robotic applications such as household robots searching for objects, inspection robots searching for leaking pipelines, and rescue robots searching for survivors after a disaster. We consider the problem of identifying and planning efficient view point sequences for covering complex 3d environments. We compare empirically several variants of our algorithm that allow to trade-off schedule computation against execution time. Our results demonstrate that, despite the intractability of the overall problem, computing effective solutions for coverage search in real 3d environments is feasible. [291] Fredrik Heintz. 2013. Semantically Grounded Stream Reasoning Integrated with ROS. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). In series: IEEE conference proceedings #??. IEEE conference proceedings. High level reasoning is becoming essential to autonomous systems such as robots. Both the information available to and the reasoning required for such autonomous systems is fundamentally incremental in nature. A stream is a flow of incrementally available information and reasoning over streams is called stream reasoning. Incremental reasoning over streaming information is necessary to support a number of important robotics functionalities such as situation awareness, execution monitoring, and decision making.This paper presents a practical framework for semantically grounded temporal stream reasoning called DyKnow. Incremental reasoning over streams is achieved through efficient progression of temporal logical formulas. The reasoning is semantically grounded through a common ontology and a specification of the semantic content of streams relative to the ontology. This allows the finding of relevant streams through semantic matching. By using semantic mappings between ontologies it is also possible to do semantic matching over multiple ontologies. The complete stream reasoning framework is integrated in the Robot Operating System (ROS) thereby extending it with a stream reasoning capability. [290] 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. [289] Andreas Kolling, Alexander Kleiner and Piotr Rudol. 2013. Fast Guaranteed Search With Unmanned Aerial Vehicles. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2013), pages 6013–6018. DOI: 10.1109/IROS.2013.6697229. In this paper we consider the problem of searching for an arbitrarily smart and fast evader in a large environment with a team of unmanned aerial vehicles (UAVs) while providing guarantees of detection. Our emphasis is on the fast execution of efficient search strategies that minimize the number of UAVs and the search time. We present the first approach for computing fast search strategies utilizing additional searchers to speed up the execution time and thereby enabling large scale UAV search. In order to scale to very large environments when using UAVs one would either have to overcome the energy limitations of UAVs or pay the cost of utilizing additional UAVs to speed up the search. Our approach is based on coordinating UAVs on sweep lines, covered by the UAV sensors, that move simultaneously through an environment. We present some simulation results that show a significant reduction in execution time when using multiple UAVs and a demonstration of a real system with three ARDrones. [288] Karen Petersen, Alexander Kleiner and Oskar von Stryk. 2013. Fast Task-Sequence Allocation for Heterogeneous Robot Teams with a Human in the Loop. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2013), pages 1648–1655. DOI: 10.1109/IROS.2013.6696570. Efficient task allocation with timing constraints to a team of possibly heterogeneous robots is a challenging problem with application, e.g., in search and rescue. In this paper a mixed-integer linear programming (MILP) approach is proposed for assigning heterogeneous robot teams to the simultaneous completion of sequences of tasks with specific requirements such as completion deadlines. For this purpose our approach efficiently combines the strength of state of the art Mixed Integer Linear Programming (MILP) solvers with human expertise in mission scheduling. We experimentally show that simple and intuitive inputs by a human user have substantial impact on both computation time and quality of the solution. The presented approach can in principle be applied to quite general missions for robot teams with human supervision. [287] Fredrik Heintz and Daniel de Leng. 2013. Semantic Information Integration with Transformations for Stream Reasoning. In 16th International Conference on Information Fusion. The automatic, on-demand, integration of informationfrom multiple diverse sources outside the control of theapplication itself is central to many fusion applications. Animportant problem is to handle situations when the requestedinformation is not directly available but has to be generatedor adapted through transformations. This paper extends thesemantic information integration approach used in the streambasedknowledge processing middleware DyKnow with supportfor finding and automatically applying transformations. Twotypes of transformations are considered. Automatic transformationbetween different units of measurements and betweenstreams of different types. DyKnow achieves semantic integrationby creating a common ontology, specifying the semantic contentof streams relative to the ontology and using semantic matchingto find relevant streams. By using semantic mappings betweenontologies it is also possible to do semantic matching overmultiple ontologies. The complete stream reasoning approach isintegrated in the Robot Operating System (ROS) and used incollaborative unmanned aircraft systems missions. [286] Mikael Nilsson. 2013. On the Complexity of Finding Spanner Paths. In Sandor P. Fekete, editor, Booklet of Abstracts, The European Workshop on Computational Geometry (EuroCG), pages 77–80. Booklet of Abstracts: http://www.ibr.cs.tu-bs.de/alg/eurocg13/... We study the complexity of finding so called spanner paths between arbitrary nodes in Euclidean graphs. We study both general Euclidean graphs and a special type of graphs called Integer Graphs. The problem is proven NP-complete for general Euclidean graphs with non-constant stretches (e.g. (2n)^(3/2) where n denotes the number of nodes in the graph). An algorithm solving the problem in O(2^(0.822n)) is presented. Integer graphs are simpler and for these special cases a better algorithm is presented. By using a partial order of so called Images the algorithm solves the spanner path problem using O(2^(c(\log n)^2)) time, where c is a constant depending only on the stretch. [285] 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). 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. [284] 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. [283] Andreas Kolling and Alexander Kleiner. 2013. Multi-UAV Trajectory Planning for Guaranteed Search. In Proc. of the 12th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2013), pages 79–86. ISBN: 978-1-4503-1993-5. We consider the problem of detecting all moving and evading targets in 2.5D environments with teams of UAVs. Targets are assumed to be fast and omniscient while UAVs are only equipped with limited range detection sensors and have no prior knowledge about the location of targets. We present an algorithm that, given an elevation map of the environment, computes synchronized trajectories for the UAVs to guarantee the detection of all targets. The approach is based on coordinating the motion of multiple UAVs on sweep lines to clear the environment from contamination, which represents the possibility of an undetected target being located in an area. The goal is to compute trajectories that minimize the number of UAVs needed to execute the guaranteed search. This is achieved by converting 2D strategies, computed for a polygonal representation of the environment, to 2.5D strategies. We present methods for this conversion and consider cost of motion and visibility constraints. Experimental results demonstrate feasibility and scalability of the approach. Experiments are carried out on real and artificial elevation maps and provide the basis for future deployments of large teams of real UAVs for guaranteed search. [282] Alexander Kleiner, A. Farinelli, S. Ramchurn, B. Shi, F. Maffioletti and R. Reffato. 2013. RMASBench: Benchmarking Dynamic Multi-Agent Coordination in Urban Search and Rescue. In Proc. of the 12th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2013), pages 1195–1196. ISBN: 978-1-4503-1993-5. We propose RMASBench, a new benchmarking tool based on the RoboCup Rescue Agent simulation system, to easily compare coordination approaches in a dynamic rescue scenario. In particular, we offer simple interfaces to plug-in coordination algorithms without the need for implementing and tuning low-level agents behaviors. Moreover, we add to the realism of the simulation by providing a large scale crowd simulator, which exploits GPUs parallel architecture, to simulate the behavior of thousands of agents in real time. Finally, we focus on a specific coordination problem where fire fighters must combat fires and prevent them from spreading across the city. We formalize this problem as a Distributed Constraint Optimization Problem and we compare two state-of-the art solution techniques: DSA and MaxSum. We perform an extensive empirical evaluation of such techniques considering several standard measures for performance (e.g. damages to buildings) and coordination overhead (e.g., message exchanged and non concurrent constraint checks). Our results provide interesting insights on limitations and benefits of DSA and MaxSum in our rescue scenario and demonstrate that RMASBench offers powerful tools to compare coordination algorithms in a dynamic environment. [281] Alexander Kleiner and Andreas Kolling. 2013. Guaranteed Search With Large Teams of Unmanned Aerial Vehicles. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pages 2977–2983. DOI: 10.1109/ICRA.2013.6630990. We consider the problem of detecting moving and evading targets by a team of coordinated unmanned aerial vehicles (UAVs) in large and complex 2D and 2.5D environments. Our approach is based on the coordination of 2D sweep lines that move through the environment to clear it from all contamination, representing the possibility of a target being located in an area, and thereby detecting all targets. The trajectories of the UAVs are implicitly given by the motion of these sweep lines and their costs are determined by the number of UAVs needed. A novel algorithm that computes low cost coordination strategies of the UAV sweep lines in simply connected polygonal environments is presented. The resulting strategies are then converted to strategies clearing multiply connected and 2.5D environments. Experiments on real and artificial elevation maps with complex visibility constraints are presented and demonstrate the feasibility and scalability of the approach. The algorithms used for the experiments are made available on a public repository. 2012 [280] Hoda Mehrpouyan, Peter Bunus and Tolga Kurtoglu. 2012. Model-Based Hazard Analysis of Undesirable Environmental and Components Interaction. In . IEEE. ISBN: 978-1-4577-0556-4. DOI: 10.1109/AERO.2012.6187374. Identifying the detrimental effect of environmental factors and subsystem interactions are historically one of the most challenging aspects of early hazard assessment in the design of complex avionic systems. Therefore, a complete understanding of potential failure effects before and even after a catastrophe happens is a very difficult task. This paper proposes a model-based hazard analysis procedure for early identification of potential safety issues caused by unexpected environmental factors and subsystem interactions within a complex avionic system. The proposed methodology maps hazard and vulnerability modes to specific components in the system and analyzes the hazard propagation paths for risk control and protection strategies. The main advantage of the proposed method is the ability to provide the designers with means to use low-fidelity, high level models to identify hazardous interactions. Using this technique, designers can examine the collective impacts of environmental and subsystem risks on overall system during early stages of design and develop a hazard mitigation strategy. [279] Cyrille Berger. 2012. Weak Constraints Network Optimiser. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 1270–1277. IEEE. DOI: 10.1109/ICRA.2012.6225060. We present a general framework to estimate the parameters of both a robot and landmarks in 3D. It relies on the use of a stochastic gradient descent method for the optimisation of the nodes in a graph of weak constraints where the landmarks and robot poses are the nodes. Then a belief propagation method combined with covariance intersection is used to estimate the uncertainties of the nodes. The first part of the article describes what is needed to define a constraint and a node models, how those models are used to update the parameters and the uncertainties of the nodes. The second part present the models used for robot poses and interest points, as well as simulation results. [278] Gerald Steinbauer and Alexander Kleiner. 2012. Towards CSP-based mission dispatching in C2/C4I systems. In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–6. IEEE. ISBN: 978-1-4799-0164-7, 978-1-4799-0163-0, 978-1-4799-0165-4. DOI: 10.1109/IROS.2007.4399131. One challenging problem in disaster response is to efficiently assign resources such as fire fighters and trucks to local incidents that are spatially distributed on a map. Existing systems for command and control (C2/C4I) are coming with powerful interfaces enabling the manual assignment of resources to the incident commander. However, with increasing number of local incidents over time the performance of manual methods departs arbitrarily from an optimal solution. In this paper we introduce preliminary results of building an interface between existing professional C2/C4I systems and Constraint Satisfaction Problem (CSP)-solvers. We show by using an example the feasibility of scheduling and assigning missions having deadlines and resource constraints. [277] 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. [276] Cyrille Berger. 2012. Toward rich geometric map for SLAM: Online Detection of Planes in 2D LIDAR. In Proceedings of the International Workshop on Perception for Mobile Robots Autonomy (PEMRA). Rich geometric models of the environment are needed for robots to accomplish their missions. However a robot operatingin a large environment would require a compact representation.In this article, we present a method that relies on the idea that a plane appears as a line segment in a 2D scan, andthat by tracking those lines frame after frame, it is possible to estimate the parameters of that plane. The method istherefore divided in three steps: fitting line segments on the points of the 2D scan, tracking those line segments inconsecutive scan and estimating the parameters with a graph based SLAM (Simultaneous Localisation And Mapping)algorithm. [275] Ha Quang-Thuy, Hoang Thi-Lan-Giao, Linh Anh Nguyen, Hung Son Nguyen, Andrzej Szalas and Tran Thanh-Luong. 2012. Concept Learning for Description Logic-based Information Systems. In KSE 2012 - International Conference on Knowledge and Systems Engineering, pages 65–73. IEEE Computer Society. DOI: 10.1109/KSE.2012.23. [274] Ha Quang-Thuy, Hoang Thi-Lan-Giao, Linh Anh Nguyen, Nguyen Hung-Son, Andrzej Szalas and Tran Thanh-Luong. 2012. A Bisimulation-based Method of Concept Learning for Knowledge Bases in Description Logics. In SoICT 2012 - 3rd International Symposium on Information and Communication Technology, pages 241–249. ACM Press. DOI: 10.1145/2350716.2350753. We develop the first bisimulation-based method of concept learning, called BBCL, for knowledge bases in description logics (DLs). Our method is formulated for a large class of useful DLs, with well-known DLs like ALC, SHIQ, SHOIQ, SROIQ. As bisimulation is the notion for characterizing indis-cernibility of objects in DLs, our method is natural and very promising. [273] Fredrik Heintz and Tommy Färnqvist. 2012. Pedagogical Experiences of Competitive Elements in an Algorithms Course. In Proceedings of LTHs 7:e Pedagogiska Inspirationskonferens (PIK). We claim that competitive elements can improve thequality of programming and algorithms courses. To test this, weused our experience from organising national and internationalprogramming competitions to design and evaluate two differentcontests in an introductory algorithms course. The first contestturned lab assignments into a competition, where two groups rancompetitions and two were control groups and did not compete.The second, voluntary, contest, consisting of 15 internationalprogramming competition style problems, was designed tosupport student skill acquisition by providing them withopportunities for deliberate practise. We found that competitiveelements do influence student behaviour and our mainconclusions from the experiment are that students really likecompetitions, that the competition design is very important forthe resulting behaviour of the students, and that active studentsperform better on exams.We also report on an extra-curricular activity in the form of asemester long programming competition as a way of supportingstudent's deliberate practise in computer programming. [272] Patrick Doherty and Fredrik Heintz. 2012. Delegation-Based Collaboration. In Proceedings of the 5th International Conference on Cognitive Systems (CogSys). [271] Fredrik Heintz and Zlatan Dragisic. 2012. Semantic Information Integration for Stream Reasoning. In Proceedings of the 15th International Conference on Information Fusion (FUSION). Linköping University Electronic Press. The main contribution of this paper is a practicalsemantic information integration approach for stream reasoningbased on semantic matching. This is an important functionality for situation awareness applications where temporal reasoning over streams from distributed sources is needed. The integration is achieved by creating a common ontology, specifying the semantic content of streams relative to the ontology and then use semantic matching to find relevant streams. By using semantic mappings between ontologies it is also possible to do semantic matching over multiple ontologies. The complete stream reasoning approach is integrated in the Robot Operating System(ROS) and used in collaborative unmanned aircraft systems missions. [270] 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 [269] 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. [268] Jonas Kvarnström. 2011. Planning for Loosely Coupled Agents Using Partial Order Forward-Chaining. In Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp, Malte Helmert, editors, Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS), pages 138–145. AAAI Press. ISBN: 978-1-57735-503-8, 978-1-57735-504-5. Fulltext: http://www.aaai.org/ocs/index.php/ICAPS/... We investigate a hybrid between temporal partial-order and forward-chaining planning where each action in a partially ordered plan is associated with a partially defined state. The focus is on centralized planning for multi-agent domains and on loose commitment to the precedence between actions belonging to distinct agents, leading to execution schedules that are flexible where it matters the most. Each agent, on the other hand, has a sequential thread of execution reminiscent of forward-chaining. This results in strong and informative agent-specific partial states that can be used for partial evaluation of preconditions as well as precondition control formulas used as guidance. Empirical evaluation shows the resulting planner to be competitive with TLplan and TALplanner, two other planners based on control formulas, while using a considerably more expressive and flexible plan structure. [267] 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. [266] Patrick Doherty and Fredrik Heintz. 2011. A Delegation-Based Cooperative Robotic Framework. In Proceedings of the IEEE International Conference on Robotics and Biomimetic. IEEE conference proceedings. [265] Jan Maluszynski and Andrzej Szalas. 2011. Living with Inconsistency and Taming Nonmonotonicity. In O. de Moor, G. Gottlob, T. Furche, A. Sellers, editors, Datalog Reloaded, pages 334–398. In series: Lecture Notes in Computer Science #6702. Springer Berlin/Heidelberg. ISBN: 978-3-642-24205-2. DOI: 10.1007/978-3-642-24206-9_22. In this paper we consider rule-based query languages with negation inbodies and heads of rules, traditionally denoted by DATALOG--. Tractable andat the same time intuitive semantics for DATALOG-- has not been provided evenif the area of deductive databases is over 30 years old. In this paper we identifysources of the problem and propose a query language, which we call 4QL.The 4QL language supports a modular and layered architecture and providesa tractable framework for many forms of rule-based reasoning both monotonicand nonmonotonic. As the underpinning principle we assume openness of theworld, which may lead to the lack of knowledge. Negation in rule heads may leadto inconsistencies. To reduce the unknown/inconsistent zones we introduce simpleconstructs which provide means for application-specific disambiguation ofinconsistent information, the use of Local Closed World Assumption (thus alsoClosed World Assumption, if needed), as well as various forms of default anddefeasible reasoning. [264] Son Thanh Cao, Linh Anh Nguyen and Andrzej Szalas. 2011. WORL: A Web Ontology Rule Language. In Proceedings of the 3rd International Conference on Knowledge and Systems Engineering (KSE), pages 32–39. IEEE. ISBN: 978-1-4577-1848-9. DOI: 10.1109/KSE.2011.14. We develop a Web ontology rule language, called WORL, which combines a variant of OWL 2 RL with eDatalog-with-negation. We disallow the features of OWL 2 RL that play the role of constraints (i.e., the ones that are translated to negative clauses), but allow additional features like negation, the minimal number restriction and unary external checkable predicates to occur in the left hand side of concept inclusion axioms. Some restrictions are adopted to guarantee a translation into eDatalog-with-negation. We also develop the well-founded semantics for WORL and the standard semantics for stratified WORL (SWORL) via translation into eDatalog-with-negation. Both WORL and SWORL have PTime data complexity. In contrast to the existing combined formalisms, in WORL and SWORL negation in concept inclusion axioms is interpreted using nonmonotonic semantics. [263] 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. [262] Son Thanh Cao, Anh Linh Nguyen and Andrzej Szalas. 2011. On the Web Ontology Rule Language OWL 2 RL. In Piotr Jedrzejowicz, Ngoc Thanh Nguyen and Kiem Hoang, editors, Proceedings of the 3rd International Conference on Computational Collective Intelligence, Technologies and Applications (ICCCI), pages 254–264. In series: Lecture Notes in Computer Science #6922. Springer Berlin/Heidelberg. ISBN: 978-3-642-23934-2. DOI: 10.1007/978-3-642-23935-9_25. It is known that the OWL 2 RL Web Ontology Language Profile has PTime data complexity and can be translated into Datalog. However, a knowledge base in OWL 2 RL may be unsatisfiable. The reason is that, when translated into Datalog, the result may consist of a Datalog program and a set of constraints in the form of negative clauses. In this paper we first identify a maximal fragment of OWL 2 RL called OWL 2 RL + with the property that every knowledge base expressed in this fragment can be translated into a Datalog program and hence is satisfiable. We then propose some extensions of OWL 2 RL and OWL 2 RL +  that still have PTime data complexity. [261] 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. [260] Alexander Kleiner, B. Nebel and V. Ziparo. 2011. A Mechanism for Dynamic Ride Sharing based on Parallel Auctions. In 22th International Joint Conference on Artificial Intelligence (IJCAI), pages 266–272. Car pollution is one of the major causes of green- house emissions, and traffic congestion is rapidly becoming a social plague. Dynamic Ride Sharing (DRS) systems have the potential to mitigate this problem by computing plans for car drivers, e.g. commuters, allowing them to share their rides. Ex- isting efforts in DRS are suffering from the problem that participants are abandoning the system after repeatedly failing to get a shared ride. In this paper we present an incentive compatible DRS solution based on auctions. While existing DRS systems are mainly focusing on fixed assignments that minimize the totally travelled distance, the presented approach is adaptive to individual preferences of the participants. Furthermore, our system allows to tradeoff the minimization of Vehicle Kilometers Travelled (VKT) with the overall probability of successful ride-shares, which is an important feature when bootstrapping the system. To the best of our knowledge, we are the first to present a DRS solution based on auctions using a sealed-bid second price scheme. [259] Q. Hamp, L. Reindl and Alexander Kleiner. 2011. Lessons Learned from German Research for USAR. In IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR). Note: Winner of the Young Author’s Award We present lessons learned in USAR research within the framework of the German research project I-LOV. After three years of development first field tests have been carried out by professionals such as the Rapid Deployment Unit for Salvage Operations Abroad (SEEBA). We present results from evaluating search teams in simulated USAR scenarios equipped with newly developed technical search means and digital data input terminals developed in the I- LOV project. In particular, the â€œbioradarâ€, a ground-penetrating radar system for the detection of humanoid movements, a semi-active video probe for rubble pile exploration of more than 10 m length, and the decision support system FRIEDAA were evaluated and compared with conventional search methods. Results of this evaluation indicate that the developed technologies foster advantages in USAR, which are discussed in this paper. [258] A. Kolling, Alexander Kleiner, M. Lewis and K. Sycara. 2011. Computing and Executing Strategies for Moving Target Search. In IEEE Int. Conf. on Robotics and Automation (ICRA), pages 4246–4253. IEEE. DOI: 10.1109/ICRA.2011.5980277. We address the problem of searching for moving targets in large outdoor environments represented by height maps. To solve the problem we present a complete system that computes from an annotated height map a graph representation and search strategies based on worst-case assumptions about all targets. These strategies are then used to compute a schedule and task assignment for all agents. We improve the graph construction from previous work and for the first time present a method that computes a schedule to minimize the execution time. For this we consider travel times of agents determined by a path planner on the height map. We demonstrate the entire system in a real environment with an area of 700,000m2 in which eight human agents search for two intruders using mobile computing devices (iPads). To the best of our knowledge this is the first demonstration of a search system applied to such a large environment. [257] D. Meyer-Delius, M. Beinhofer, Alexander Kleiner and W. Burgard. 2011. Using artificial landmarks to reduce the ambiguity in the environment of a mobile robot. In IEEE Int. Conf. on Robotics and Automation (ICRA), pages 5173–5178. DOI: 10.1109/ICRA.2011.5980111. Robust and reliable localization is a fundamental prerequisite for many applications of mobile robots. Although there exist many solutions to the localization problem, structurally symmetrical or featureless environments can prevent different locations from being distinguishable given the data obtained with the robot’s sensors. Such ambiguities typically make localization approaches more likely to fail. In this paper, we investigate how artificial landmarks can be utilized to reduce the ambiguity in the environment. We present a practical approach to compute a configuration of indistinguishable landmarks that decreases the overall ambiguity and thus increases the robustness of the localization process. We evaluate our approach in different environments based on real data and in simulation. Our results demonstrate that our approach improves the localization performance of the robot and outperforms other landmark selection approaches. [256] Alexander Kleiner, D. Sun and D. Meyer-Delius. 2011. ARMO - Adaptive Road Map Optimization for Large Robot Teams. In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 3276–3282. IEEE conference proceedings. DOI: 10.1109/IROS.2011.6048339. Autonomous robot teams that simultaneously dispatch transportation tasks are playing more and more an important role in present logistic centers and manufacturing plants. In this paper we consider the problem of robot motion planning for large robot teams in the industrial domain. We present adaptive road map optimization (ARMO) that is capable of adapting the road map in real time whenever the environment has changed. Based on linear programming, ARMO computes an optimal road map according to current environmental constraints (including human whereabouts) and the current demand for transportation tasks from loading stations in the plant. For detecting dynamic changes, the environment is describe by a grid map augmented with a hidden Markov model (HMM). We show experimentally that ARMO outperforms decoupled planning in terms of computation time and time needed for task completion. 2010 [255] Barbara Dunin-Keplicz, Anh Linh Nguyen and Andrzej Szalas. 2010. Graded Beliefs, Goals and Intentions. In Proceedings of the 3rd Workshop on Logical Aspects of Multi-Agent Systems (LAMAS), pages 1–15. AAAI Press. [254] Cyrille Berger and Simon Lacroix. 2010. DSeg: Détection directe de segments dans une image. In 17ème congrès francophone AFRIF-AFIA Reconnaissance des Formes et Intelligence Artificielle (RFIA). Cet article présente une approche model-driven'' pour détecter des segmentsde droite dans une image. L'approche détecte les segments de manièreincrémentale sur la base du gradient de l'image, en exploitant un filtre deKalman linéaire qui estime les paramètres de la droite support des segments etles variances associées. Les algorithmes sont rapides et robustes au bruit etaux variations d'illumination de la scène perçue, ils permettent de détecterdes segments plus longs que les approches existantes guidées par les données(data-driven''), et ils ne nécessitent pas de délicate détermination deparamètres. Des résultats avec différentes conditions d'éclairage et descomparaisons avec les approches existantes sont présentés. [253] Prasanna Velagapudi, Alexander Kleiner, Nathan Brooks, Paul Scerri, Michael Lewis and Katia Sycara. 2010. RoboCupRescue - Virtual Robots Team STEEL (USA). In RoboCup 2010 (CDROM Proceedings), Team Description Paper, Rescue Simulation League. This paper describes the software system supporting the Carnegie Mellon/Univ. of Pittsburgh team of simulated search and rescue robots in the Robocup Rescue 2010 Virtual Robots competition. Building on the Machinetta agent software, robot command and control is decomposed into a hierarchy of subtasks managed by independent agents both on the robot and co-located with human operators. By encapsulating all robot and human operator interactions into interfaces to these agents, the system can perform with a high level of robustness and re-usability. As in previous years, the entire code base is portable and platform-independent, running entirely in Java. [252] Christian Dornhege, Johannes Bendler, Roxana Bersan, Philipp Blohm, Martin Gloderer, Andreas Hertle, Thomas Liebetraut, Diego Cerdan Puyol, Alexander Kleiner and Bernhard Nebel. 2010. RoboCupRescue 2010 - Robot League Team RescueRobots Freiburg (Germany). In RoboCup 2010 (CDROM Proceedings), Team Description Paper, Rescue Robot League. This paper describes the software and hardware system developed by the University of Freiburg team of search and rescue robots for the RoboCup Res- cue 2010 competition. This system is an extension to the software that finished in first place the 2005 and 2006 autonomy challenge, focusing on two key areas: autonomous navigation and manipulation. Our team, consisting mainly of students, originates from the former CS Freiburg team (RoboCupSoccer), the ResQ Freiburg team (RoboCupRescue Simulation), and RescueRobots Freiburg teams â€™05 and â€™06. [251] Wei Mou and Alexander Kleiner. 2010. Online Learning Terrain Classification for Adaptive Velocity Control. In In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–7. DOI: 10.1109/SSRR.2010.5981563. Safe teleoperation during critical missions, such as urban search and rescue and bomb disposal, requires careful velocity control when different types of terrain are found in the scenario. This can particularly be challenging when mission time is limited and the operator’s field of view affected. This paper presents a method for online adapting robot velocities according to the terrain classification from vision and laser readings. The classifier adapts itself to illumination variations, and can be improved online given feedback from the operator. [250] Sören Schwertfeger, Adam Jacoff, Chris Scrapper, Johannes Pellenz and Alexander Kleiner. 2010. Evaluation of Maps using Fixed Shapes: The Fiducial Map Metric. In Proc. of the Int. Workshop on Performance Metrics for Intelligent Systems (PerMIS), pages 344–351. NIST. Mapping is an important task for mobile robots. Assessing the quality of those maps is an open topic. A new approach on map evaluation is presented here. It makes use of artificial objects placed in the environment named \"Fiducials\". Using the known ground-truth positions and the positions of the fiducials identified in the map, a number of quality attributes can be assigned to that map. Depending on the application domain those attributes are weighed to compute a final score. During the 2010 NIST Response Robot Evaluation Exercise at Disaster City an area was populated with fiducials and different mapping runs were performed. The maps generated there are assessed in this paper demonstrating the Fiducial approach. Finally this map scoring algorithm is compared to other approaches found in literature. [249] A. Kolling, Alexander Kleiner, M. Lewis and K. Sycara. 2010. Solving Pursuit-Evasion Problems on Height Maps. In IEEE International Conference on Robotics and Automation (ICRA 2010) Workshop: Search and Pursuit/Evasion in the Physical World: Efficiency, Scalability, and Guarantees. IEEE. In this paper we present an approach for a pursuit-evasion problem that considers a 2.5d environment represented by a height map. Such a representation is particularly suitable for large-scale outdoor pursuit-evasion. By allowing height information we not only capture some aspects of 3d visibility but can also consider target heights. In our approach we construct a graph representation of the environment by sampling points and their detection sets which extend the usual notion of visibility. Once a graph is constructed we compute strategies on this graph using a modification of previous work on graph-searching. This strategy is converted into robot paths that are planned on the height map by classifying the terrain appropriately. In experiments we investigate the performance of our approach and provide examples including a map of a small village with surrounding hills and a sample map with multiple loops and elevation plateaus. Experiments are carried out with varying sensing ranges as well as target and sensor heights. To the best of our knowledge the presented approach is the first viable solution to 2.5d pursuit-evasion with height maps. [248] D. Maier and Alexander Kleiner. 2010. Improved GPS Sensor Model for Mobile Robots in Urban Terrain. In IEEE Int. Conf. on Robotics and Automation (ICRA), pages 4385–4390. IEEE. ISBN: 978-1-4244-5038-1. DOI: 10.1109/ROBOT.2010.5509895. Autonomous robot navigation in outdoor scenarios gains increasing importance in various growing application areas. Whereas in non-urban domains such as deserts the problem of successful GPS-based navigation appears to be almost solved, navigation in urban domains particularly in the close vicinity of buildings is still a challenging problem. In such situations GPS accuracy significantly drops down due to multiple signal reflections with larger objects causing the so-called multipath error. In this paper we contribute a novel approach for incorporating multi- path errors into the conventional GPS sensor model by analyzing environmental structures from online generated point clouds. The approach has been validated by experimental results conducted with an all- terrain robot operating in scenarios requiring close- to-building navigation. Presented results show that positioning accuracy can significantly be improved within urban domains. [247] A. Kolling, Alexander Kleiner, M. Lewis and K. Sycara. 2010. Pursuit-Evasion in 2.5d based on Team-Visibility. In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 4610–4616. IEEE. ISBN: 978-1-4244-6674-0. DOI: 10.1109/IROS.2010.5649270. In this paper we present an approach for a pursuit-evasion problem that considers a 2.5d environment represented by a height map. Such a representation is particularly suitable for large-scale outdoor pursuit-evasion, captures some aspects of 3d visibility and can include target heights. In our approach we construct a graph representation of the environment by sampling points and computing detection sets, an extended notion of visibility. Moreover, the constructed graph captures overlaps of detection sets allowing for a coordinated team-based clearing of the environment with robots that move to the sampled points. Once a graph is constructed we compute strategies on it utilizing previous work on graph-searching. This is converted into robot paths that are planned on the height map by classifying the terrain appropriately. In experiments we investigate the performance of our approach and provide examples including a sample map with multiple loops and elevation plateaus and two realistic maps, one of a village and one of a mountain range. To the best of our knowledge the presented approach is the first viable solution to 2.5d pursuit-evasion with height maps. [246] D. Sun, Alexander Kleiner and C. Schindelhauer. 2010. Decentralized Hash Tables For Mobile Robot Teams Solving Intra-Logistics Tasks. In 9th Int. Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), pages 923–930. International Foundation for Autonomous Agents and. Although a remarkably high degree of automation has been reached in production and intra-logistics nowadays, human labor is still used for transportation using handcarts and forklifts. High labor cost and risk of injury are the undesirable consequences. Alternative approaches in automated warehouses are fixed installed conveyors installed either overhead or floor-based. The drawback of such solutions is the lack of flexibility, which is necessary when the production lines of the company change. Then, such an installation has to be re-built. In this paper, we propose a novel approach of decentralized teams of autonomous robots performing intra-logistics tasks using distributed algorithms. Centralized solutions suffer from limited scalability and have a single point of failure. The task is to transport material between stations keeping the communication network structure intact and most importantly, to facilitate a fair distribution of robots among loading stations. Our approach is motivated by strategies from peer-to-peer-networks and mobile ad-hoc networks. In particular we use an adapted version of distributed heterogeneous hash tables (DHHT) for distributing the tasks and localized communication. Experimental results presented in this paper show that our method reaches a fair distribution of robots over loading stations. [245] Anh Linh Nguyen and Andrzej Szalas. 2010. Three-Valued Paraconsistent Reasoning for Semantic Web Agents. In Proceedings of the 4th International KES Symposium on Agents and Multi-agent Systems – Technologies and Applications (KES-AMSTA), pages 152–162. In series: Lecture Notes in Artificial Intelligence #6070. Springer. ISBN: 978-3-642-13479-1. DOI: 10.1007/978-3-642-13480-7_17. Description logics [1] refer to a family of formalisms concentrated around concepts, roles and individuals. They are used in many multiagent and semantic web applications as a foundation for specifying knowledge bases and reasoning about them. One of widely applied description logics is SHIQ [7,8]. In the current paper we address the problem of inconsistent knowledge. Inconsistencies may naturally appear in the considered application domains, for example as a result of fusing knowledge from distributed sources. We define three three-valued paraconsistent semantics for SHIQ, reflecting different meanings of concept inclusion of practical importance. We also provide a quite general syntactic condition of safeness guaranteeing satisfiability of a knowledge base w.r.t. three-valued semantics and define a faithful translation of our formalism into a suitable version of a two-valued description logic. Such a translation allows one to use existing tools and SHIQ reasoners to deal with inconsistent knowledge. [244] 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. [243] 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. [242] 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. [241] 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. [240] 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). 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. [239] 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. [238] 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. [237] 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. [236] 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. [235] Håkan Warnquist, Jonas Kvarnström and Patrick Doherty. 2010. Iterative Bounding LAO*. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI), pages 341–346. In series: Frontiers in Artificial Intelligence and Applications #215. IOS Press. ISBN: 978-1-60750-605-8, 978-1-60750-606-5. 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. [234] Jonas Kvarnström. 2010. Planning for Loosely Coupled Agents using Partial Order Forward-Chaining. In Roland Bol, editor, The Swedish AI Society Workshop 2010, SAIS 2010, pages 45–54. In series: Linköping Electronic Conference Proceedings #48. Linköping University Electronic Press, Linköpings universitet. Fulltext: http://www.ep.liu.se/ecp/048/009/ecp1048... Partially ordered plan structures are highly suitable for centralized multi-agent planning, where plans should be minimally constrained in terms of precedence between actions performed by different agents. In many cases, however, any given agent will perform its own actions in strict sequence. We take advantage of this fact to develop a hybrid of temporal partial order planning and forward-chaining planning. A sequence of actions is constructed for each agent and linked to other agents' actions by a partially ordered precedence relation as required. When agents are not too tightly coupled, this structure enables the generation of partial but strong information about the state at the end of each agent's action sequence. Such state information can be effectively exploited during search. A prototype planner within this framework has been implemented, using precondition control formulas to guide the search process. [233] 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? [232] 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 [231] Barbara Dunin-Keplicz, Linh Anh Nguyen and Andrzej Szalas. 2009. Fusing Approximate Knowledge from Distributed Sources. In Proceedings of the 3rd International Symposium on Intelligent Distributed Computing (IDC), pages 75–86. In series: Studies in Computational Intelligence #237. Springer Berlin/Heidelberg. ISBN: 978-3-642-03213-4, 978-3-642-26930-1. DOI: 10.1007/978-3-642-03214-1_8. In this paper we investigate a technique for fusing approximate knowledge obtained from distributed, heterogeneous information sources. We use a generalization of rough sets and relations [14], which depends on allowing arbitrary similarity relations. The starting point of this research is [2], where a framework for knowledge fusion in multi-agent systems is introduced. Agent’s individual perceptual capabilities are represented by similarity relations, further aggregated to express joint capabilities of teams. This aggregation, allowing a shift from individual to social level, has been formalized by means of dynamic logic. The approach of [2] uses the full propositional dynamic logic, not guaranteeing the tractability of reasoning. Therefore the results of [11, 12, 13] are adapted to provide a technical engine for tractable approximate database querying restricted to a Horn fragment of serial PDL. We also show that the obtained formalism is quite powerful in applications. [230] Linh Anh Nguyen and Andrzej Szalas. 2009. Checking Consistency of an ABox w.r.t. Global Assumptions in PDL*. In Proceedings of the 18th Concurrency, Specification and Programming Workshop (CS&P), pages 431–442. [229] Linh Anh Nguyen and Andrzej Szalas. 2009. An Optimal Tableau Decision Procedure for Converse-PDL. In Proceedings of the 1st International Conference on Knowlegde and Systems Engineering (KSE), pages 207–214. IEEE Computer Society. ISBN: 978-1-4244-5086-2. DOI: 10.1109/KSE.2009.12. We give a novel tableau calculus and an optimal (EXPTIME) tableau decision procedure based on the calculus for the satisfiability problem of propositional dynamic logic with converse. Our decision procedure is formulated with global caching and can be implemented together with useful optimization techniques. [228] Teresa Vidal-Calleja, Cyrille Berger, Joan Solà and Simon Lacroix. 2009. Environment Modeling for Cooperative Aerial/Ground Robotic Systems. In Proceedings of the 14th International Symposium on Robotics Research (ISRR), pages 681–696. In series: Springer Tracts in Advanced Robotics #70. Springer. ISBN: 978-3-642-19456-6. DOI: 10.1007/978-3-642-19457-3_40. This paper addresses the cooperative localization and visual mapping problem for multiple aerial and ground robots.We propose the use of heterogeneous visual landmarks, points and line segments. A large-scale SLAM algorithm is generalized to manage multiple robots, in which a global graph maintains the topological relationships between a series of local sub-maps built by the different robots. Only single camera setups are considered: in order to achieve undelayed initialization, we present a novel parametrization for lines based on anchored Plücker coordinates, to which we add extensible endpoints to enhance their representativeness. The built maps combine such lines with 3D points parametrized in inverse-depth. The overall approach is evaluated with real-data taken with a helicopter and a ground rover in an abandoned village. [227] Teresa Vidal-Calleja, Cyrille Berger and Simon Lacroix. 2009. Event-driven loop closure in multi-robot mapping. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1535–1540. IEEE conference proceedings. ISBN: 978-1-4244-3803-7. DOI: 10.1109/IROS.2009.5354335. A large-scale mapping approach is combined with multiple robots events to achieve cooperative mapping. The mapping approach used is based on hierarchical SLAM -global level and local maps-, which is generalized for the multi-robot case. In particular, the consequences of multi-robot loop closing events (common landmarks detection and relative pose measurement between robots) are analyzed and managed at a global level. We present simulation results for each of these events using aerial and ground robots, and experimental results obtained with ground robots. [226] Alexander Kleiner, Chris Scrapper and Adam Jacoff. 2009. RoboCupRescue Interleague Challenge 2009: Bridging the gap between Simulation and Reality. In In Proc. of the Int. Workshop on Performance Metrics for Intelligent Systems (PerMIS), pages 123–129. The RoboCupRescue initiative, represented by real-robot and simulation league, is designed to foster the research and development of innovative technologies and assistive capabilities to help responders mitigate an emergency response situation. This competition model employed by the RobocupRescue community has proven to be a propitious model, not only for fostering the development of innovative technologies but in the development of test methods used to quantitatively evaluate the performance of these technologies. The Interleague Challenge has been initiated to evaluate real-world performance of algorithms developed in simulation, as well as to drive the development of a common interface to simplify the entry of newcomer teams to the robot league. This paper will discuss the development of emerging test methods used to evaluate robotic-mapping, the development of a common robotic platform, and the development of a novel map evaluation methodology deployed during the RoboCupRescue competition 2009. [225] Dali Sun, Alexander Kleiner and Thomas M. Wendt. 2009. Multi-Robot Range-Only SLAM by Active Sensor Nodes for Urban Search and Rescue. In Robocup 2008: Robot Soccer World Cup XII, pages 318–330. To jointly map an unknown environment with a team of autonomous robots is a challenging problem, particularly in large environments, as for example the devastated area after a disaster. Under such conditions standard methods for Simultaneous Localization And Mapping (SLAM) are difficult to apply due to possible misinterpretations of sensor data, leading to erroneous data association for loop closure. We consider the problem of multi-robot range-only SLAM for robot teams by solving the data association problem with wireless sensor nodes that we designed for this purpose. The memory of these nodes is utilized for the exchange of map data between multiple robots, facilitating loop-closures on jointly generated maps. We introduce RSLAM, which is a variant of FastSlam, extended for range-only measurements and the multi-robot case. Maps are generated from robot odometry and range estimates, which are computed from the RSSI (Received Signal Strength Indication). The proposed method has been extensively tested in USARSim, which serves as basis for the Virtual Robots competition at RoboCup, and by real-world experiments with a team of mobile robots. The presented results indicates that the approach is capable of building consistent maps in presence of real sensor noise, as well as to improve mapping results of multiple robots by data sharing. [224] W. Burgard, C. Stachniss, G. Grisetti, B. Steder, R. Kümmerle, C. Dornhege, M. Ruhnke, Alexander Kleiner and Juan D. Tardós. 2009. A Comparison of SLAM Algorithms Based on a Graph of Relations. In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 2089–2095. IEEE conference proceedings. DOI: 10.1109/IROS.2009.5354691. In this paper, we address the problem of creating an objective benchmark for comparing SLAM approaches. We propose a framework for analyzing the results of SLAM approaches based on a metric for measuring the error of the corrected trajectory. The metric uses only relative relations between poses and does not rely on a global reference frame. The idea is related to graph-based SLAM approaches, namely to consider the energy that is needed to deform the trajectory estimated by a SLAM approach into the ground truth trajectory. Our method enables us to compare SLAM approaches that use different estimation techniques or different sensor modalities since all computations are made based on the corrected trajectory of the robot. We provide sets of relative relations needed to compute our metric for an extensive set of datasets frequently used in the SLAM community. The relations have been obtained by manually matching laser-range observations to avoid the errors caused by matching algorithms. Our benchmark framework allows the user an easy analysis and objective comparisons between different SLAM approaches. [223] Alexander Kleiner and C. Dornhege. 2009. Operator-Assistive Mapping in Harsh Environments. In IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–6. IEEE. ISBN: 978-1-4244-5627-7. DOI: 10.1109/SSRR.2009.5424159. Note: (Best Paper Award Finalist) Teleoperation is a difficult task, particularly when controlling robots from an isolated operator station. In general, the operator has to solve nearly blindly the problems of mission planning, target identification, robot navigation, and robot control at the same time. The goal of the proposed system is to support teleoperated navigation with real-time mapping. We present a novel scan matching technique that re-considers data associations during the search, enabling robust pose estimation even under varying roll and pitch angle of the robot enabling mapping on rough terrain. The approach has been implemented as an embedded system and extensively tested on robot platforms designed for teleoperation in critical situations, such as bomb disposal. Furthermore, the system has been evaluated in a test maze by first responders during the Disaster City event in Texas 2008. Finally, experiments conducted within different environments show that the system yields comparably accurate maps in real-time when compared to higher sophisticated offline methods, such as Rao-Blackwellized SLAM. [222] R. Kümmerle, B. Steder, C. Dornhege, Alexander Kleiner, G. Grisetti and W. Burgard. 2009. Large Scale Graph-based SLAM using Aerial Images as Prior Information. In Proceedings of Robotics Science and Systems (RSS). MIT Press. To effectively navigate in their environments and accurately reach their target locations, mobile robots require a globally consistent map of the environment. The problem of learning a map with a mobile robot has been intensively studied in the past and is usually referred to as the simultaneous localization and mapping (SLAM) problem. However, existing solutions to the SLAM problem typically rely on loop-closures to obtain global consistency and do not exploit prior information even if it is available. In this paper, we present a novel SLAM approach that achieves global consistency by utilizing publicly accessible aerial photographs as prior information. Our approach inserts correspondences found between three-dimensional laser range scans and the aerial image as constraints into a graph-based formulation of the SLAM problem. We evaluate our algorithm based on large real-world datasets acquired in a mixed in- and outdoor environment by comparing the global accuracy with state-of-the-art SLAM approaches and GPS. The experimental results demonstrate that the maps acquired with our method show increased global consistency. [221] Anna Pernestål, Håkan Warnquist and Mattias Nyberg. 2009. Modeling and Troubleshooting with Interventions Applied to an Auxiliary Truck Braking System. In Proceedings of the 2nd IFAC Workshop on Dependable Control of Discrete Systems (DCDS). [220] 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. [219] Håkan Warnquist, Anna Pernestål and Mattias Nyberg. 2009. Anytime Near-Optimal Troubleshooting Applied to a Auxiliary Truck Braking System. In Proceedings of the 7th IFAC Symposium on Fault Detection, Supervision and Safety of Technical Processes, pages 1306–1311. We consider computer assisted troubleshooting of complex systems, for example of a vehicle at a workshop. The objective is to identify the cause of a failure and repair a system at as low expected cost as possible. Three main challenges are: the need for disassembling the system during troubleshooting, the difficulty to verify that the system is fault free, and the dependencies in between components and observations. We present a method that can return a response anytime, which allows us to obtain the best result given the available time. The work is based on a case study of an auxiliary braking system of a modern truck. We highlight practical issues related to model building and troubleshooting in a real environment. [218] 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). [217] 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. [216] 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. [215] Andrzej Szalas and Linh Anh Nguyen. 2009. EXPTIME Tableaux for Checking Satisfiability of a Knowledge Base in the Description Logic ALC. In Ngoc Thanh; Kowalczyk, Ryszard; Chen, Shyi-Ming, editors, Proceedings of the 1st International Conference on Computational Collective Intelligence - Semantic Web, Social Networks & Multiagent Systems (ICCCI), pages 437–448. In series: Lecture Notes in Artificial Intelligence #5796. Springer. ISBN: 978-3-642-04440-3. DOI: 10.1007/978-3-642-04441-0_38. We give the first ExpTime (optimal) tableau decision procedure for checking satisfiability of a knowledge base in the description logic ALC, not based on transformation that encodes ABoxes by nominals or terminology axioms. Our procedure can be implemented as an extension of the highly optimized tableau prover TGC [12] to obtain an efficient program for the mentioned satisfiability problem. [214] 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. [213] 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... [212] M. Wiggberg and Peter Dalenius. 2009. Bridges and problem solving: Swedish engineering students' conceptions of engineering in 2007. In Proceedings of the 1st International Conference on Computer Supported Education (CSEDU), pages 5–12. ISBN: 978-989-8111-82-1. Swedish engineering students conceptions of engineering is investigated by a large nation-wide study in ten Swedish higher education institutions. Based on data from surveys and interviews, categories and top-lists, a picture of students conceptions of engineering is presented. Students conceptions of engineering, are somewhat divergent, but dealing with problems and their solutions and creativity are identified as core concepts. The survey data is in general more varied and deals with somewhat different kinds of terms. When explicitly asking for five engineering terms, as in the survey, a broader picture arises including terms, or concepts, denoting how students think of engineering and work in a more personal way. For example, words like hard work, stressful, challenging, interesting, and fun are used. On the other hand, it seems like the interviewed students tried to give more general answers that were not always connected to their personal experiences. Knowledge on students conceptions of engineering is essential for practitioners in engineering education. By information on students conceptions, the teaching can approach students at their particular mindset of the engineering field. Program managers with responsibility for design of engineering programs would also benefit using information on students conceptions of engineering. Courses could be motivated and contextualized in order to connect with the students. Recruitment officers would also have an easier time marketing why people should chose the engineering track. [211] Linh Anh Nguyen and Andrzej Szalas. 2009. A tableau calculus for regular grammar logics with converse. In Proceedings of the 22nd International Conference on Automated Deduction (CADE), pages 421–436. In series: Lecture Notes in Artificial Intelligence #5663. Springer. ISBN: 978-364202958-5. DOI: 10.1007/978-3-642-02959-2_31. We give a sound and complete tableau calculus for deciding the general satisfiability problem of regular grammar logics with converse (REG c logics). Tableaux of our calculus are defined as \"and-or\" graphs with global caching. Our calculus extends the tableau calculus for regular grammar logics given by Goré and Nguyen [11] by using a cut rule and existential automaton-modal operators to deal with converse. We use it to develop an ExpTime (optimal) tableau decision procedure for the general satisfiability problem of REG c logics. We also briefly discuss optimizations for the procedure. 2008 [210] 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. [209] Cyrille Berger and Simon Lacroix. 2008. Modélisation de l'environnement par facettes planes pour la Cartographie et la Localisation Simultanées par stéréovision. In Reconnaissance des Formes et Intelligence Artificielle (RFIA). [208] Cyrille Berger and Simon Lacroix. 2008. Using planar facets for stereovision SLAM. In Proceedings of the IEEE/RSJ International Conference on Intelligent RObots and Systems (IROS), pages 1606–1611. IEEE conference proceedings. ISBN: 978-1-4244-2057-5. DOI: 10.1109/IROS.2008.4650986. In the context of stereovision SLAM, we propose a way to enrich the landmark models. Vision-based SLAM approaches usually rely on interest points associated to a point in the Cartesian space: by adjoining oriented planar patches (if they are present in the environment), we augment the landmark description with an oriented frame. Thanks to this additional information, the robot pose is fully observable with the perception of a single landmark, and the knowledge of the patches orientation helps the matching of landmarks. The paper depicts the chosen landmark model, the way to extract and match them, and presents some SLAM results obtained with such landmarks. [207] Christian Dornhege, Alexander Kleiner, Rainer Kümmerle, Bastian Steder, Wolfram Burgard and Bernhard Nebel. 2008. SP-Freiburg TechX Challenge Technical Paper. In TechX Challenge. Note: Finalist In this paper we introduce our team’s approach to the TechX Challenge, which is based on experiences gathered at RoboCup during the last seven years and recent efforts in robotic research. We particularly focus on Multi-Level Surface (MLS) maps based localization, behavior map based path planning and obstacle negotiation, robot motion planning using a probabilistic roadmap planner, vision and 3D laser supported target detection, which all will be more detailed in the following sections. [206] Alexander Kleiner, Gerald Steinbauer and Franz Wotawa. 2008. Towards Automated Online Diagnosis of Robot Navigation Software. In Proc. of Int. Conf. on Simulation, Modeling and Programming for Autonomous Robots (SIMPAR), pages 159–170. In series: Lecture Notes in Computer Science #5325. Springer. DOI: 10.1007/978-3-540-89076-8_18. Control software of autonomous mobile robots comprises a number of software modules that typically interact in a very complex way. Their proper interaction and the robustness of each single module strongly influences the safety during navigation in the field. Particularly in unstructured environments, unforeseen situations are likely to occur, causing erroneous behaviors of the robot. The proper handling of such situations requires an understanding of cause and effect within the complex interactions of the system. In this paper we present an approach which is able to automatically derive a model of the communication behavior within a component-orientated control software. The model can be used for online diagnosis in order to increase system robustness during runtime. We demonstrate model learning and system diagnosis on three different robot systems which were controlled by software modules communicating based on the widely used IPC (Inter Process Communication) standard. The demonstrated learning and diagnosis was carried out without any a priori knowledge about the systems. [205] Alexander Kleiner, Gerald Steinbauer and Franz Wotawa. 2008. Automated Learning of Communication Models for Robot Control Software. In MBS 2008 - Workshop on Model-Based Systems, 18th European Conference on Artificial Intelligence (ECAI). Control software of autonomous mobile robots comprises a number of software modules which show very rich behaviors and interact in a very complex manner. These facts among others have a strong influence on the robustness of robot con- trol software in the field. In this paper we present an approach which is able to automatically derive a model of the structure and the behavior of the communication within a component- orientated control software. Such a model can be used for on-line model-based diagnosis in order to increase the robust- ness of the software by allowing the robot to autonomously cope with faults occurred during runtime. Due to the fact that the model is learned form recorded data and the use of the popular publisher-subscriber paradigm the approach can be applied to a wide range of complex and even partially un- known systems. [204] Anders Holmberg and Per-Magnus Olsson. 2008. Route Planning for Relay UAV. In Proceedings of the 26th International Congress of the Aeronautical Sciences (ICAS). Optimage Ltd.. ISBN: ISBN 0-9533991-9-2. To expand the operative area for surveillance UAV, we propose the use of a relay UAV. The relay UAV is used as an intermediary node in a communication network: the surveillance UAV transmits data to the relay UAV, which sends it back to a ground station. In this exploratory report, we calculate the route for a relay UAV, to ensure communication at certain time points, given the route of the surveillance UAV. The results presented here are preliminary and may be considered a first iteration of ideas and methods. [203] Joe Steinhauer. 2008. Object Configuration Reconstruction from Descriptions using Relative and Intrinsic Reference Frames. In ECAI 2008, pages 821–822. 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-821. We provide a technique to reconstruct an object configuration that has been described on site by only using intrinsic and relative frames of reference into an absolute frame of reference, as seen from the survey perspective. [202] 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. [201] Håkan Warnquist and Mattias Nyberg. 2008. A Heuristic for Near-Optimal Troubleshooting Using AO*. In Proceedings of the International Workshop on the Principles of Diagnosis. When troubleshooting malfunctioning technical equipment, the task is to locate faults and make repairsuntil the equipment functions properly again. The AO* algorithm can be used to find troubleshootingstrategies that are optimal in the sense that the expected cost of repair is minimal. We have adaptedthe AO* algorithm for troubleshooting in the automotive domain with limited time. We propose a newheuristic based on entropy. By using this heuristic, near-optimal strategies can be found within a fixedtime limit. This is shown in empirical studies on a fuel injection system of a truck. In these results, theAO* algorithm using the new heuristic, performs better than other troubleshooting algorithms. [200] Håkan Warnquist, Mattias Nyberg and Petter Säby. 2008. Troubleshooting when Action Costs are Dependent with Application to a Truck Engine. In 10th Scandinavian Conference on Artificial Intelligence, SCAI 2008, pages 68–75. 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 propose a troubleshooting algorithm that can troubleshoot systems with dependent action costs. When actions are performed they may change the way the system is decomposed and affect the cost of future actions. We present a way to model this by extending the traditional troubleshooting model with an additional state that describes which parts of the system that are decomposed. The proposed troubleshooting algorithm searches an AND/OR graph with the aim of finding the repair plan that minimizes the expected cost of repair. We present the heuristics needed to speed up the search and make it competitive with other troubleshooting algorithms. Finally, the performance of the algorithm is evaluated on a probabilistic model of a fuel injection system of a truck.We show that the expected cost of repair can be reduced when compared with an algorithm from previous literature. [199] 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. [198] 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. [197] 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 conference proceedings. ISBN: 978-1-4244-1487-1. 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. [196] Erik Sandewall. 2008. Artificial Intelligence Needs Open-Access Knowledgebase Contents. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), pages 1602–1605. AAAI Press. ISBN: 978-1-57735-368-3, 978-1-57735-367-6. Note: Senior Members track A substantial knowledgebase is an important part of many A.I. applications as well as (arguably) in any system that is claimed to implement broad-range intelligence. Although this has been an accepted view in our field since very long, little progress has been made towards the establishment of large and sharable knowledgebases. Both basic research projects and applications projects have found it necessary to construct special-purpose knowledgebases for their respective needs. This is obviously a problem: it would save work and speed up progress if the construction of a broadly sharable and broadly useful knowledgebase could be a joint undertaking for the field. In this article I wish to discuss the possibilities and the obstacles in this respect. I shall argue that the field of Knowledge Representation needs to adopt a new and very different paradigm in order for progress to be made, so that besides working as usual on logical foundations and on algorithms, we should also devote substantial efforts to the systematic preparation of knowledgebase contents. [195] 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. [194] H.Joe Steinhauer. 2008. Object Configuration Reconstruction from Incomplete Binary Object Relation Descriptions. In Dengel, A.; Berns, K.; Breuel, Th.; Bomarius, F.; Roth-Berghofer, Th.R., editors, Proceedings of the 31st German Conference on Advances in Artificial Intelligence (KI), pages 348–355. In series: Lecture Notes in Computer Science #5243. Springer. ISBN: 978-3-540-85844-7. DOI: 10.1007/978-3-540-85845-4_43. We present a process for reconstructing object configurations described by a set of spatial constraints of the form (A northeast B) into a two-dimensional grid. The reconstruction process is cognitively easy for a person to fulfill and guides the user to avoid typical mistakes. For underspecified object configuration descriptions we suggest a strategy to handle coarse object relationships by representing a coarse object in a way that all disjunctive basic relationships that the coarse relationship consists of are represented within one reconstruction. [193] 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. [192] 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. [191] 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. [190] 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. [189] 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. [188] 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. [187] 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. [186] 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. [185] Rickard Karlsson, Thomas Schön, David Törnqvist, Gianpaolo Conte and Fredrik Gustafsson. 2008. Utilizing Model Structure for Efficient Simultaneous Localization and Mapping for a UAV Application. In Proceedings of the 2008 IEEE Aerospace Conference, pages 1–10. ISBN: 978-1-4244-1487-1, 978-1-4244-1488-8. DOI: 10.1109/AERO.2008.4526442. Related report: http://urn.kb.se/resolve?urn=urn:nbn:se:... This contribution aims at unifying two recent trends in applied particle filtering (PF). The first trend is the major impact in simultaneous localization and mapping (SLAM) applications, utilizing the FastSLAM algorithm. The second one is the implications of the marginalized particle filter (MPF) or the Rao-Blackwellized particle filter (RBPF) in positioning and tracking applications. Using the standard FastSLAM algorithm, only low-dimensional vehicle models are computationally feasible. In this work, an algorithm is introduced which merges FastSLAM and MPF, and the result is an algorithm for SLAM applications, where state vectors of higher dimensions can be used. Results using experimental data from a UAV (helicopter) are presented. The algorithm fuses measurements from on-board inertial sensors (accelerometer and gyro) and vision in order to solve the SLAM problem, i.e., enable navigation over a long period of time. [184] Mattias Krysander, Fredrik Heintz, Jacob Roll and Erik Frisk. 2008. Dynamic Test Selection for Reconfigurable Diagnosis. In Proceedings of the 47th IEEE Conference on Decision and Control, pages 1066–1072. In series: IEEE Conference on Decision and Control. Proceedings #??. IEEE. ISBN: 978-1-4244-3124-3, 978-1-4244-3123-6. DOI: 10.1109/CDC.2008.4738793. Detecting and isolating multiple faults is a computationally intense task which typically consists of computing a set of tests, and then computing the diagnoses based on the test results. This paper proposes a method to reduce the computational burden by only running the tests that are currently needed, and dynamically starting new tests when the need changes. A main contribution is a method to select tests such that the computational burden is reduced while maintaining the isolation performance of the diagnostic system. Key components in the approach are the test selection algorithm, the test initialization procedures, and a knowledge processing framework that supports the functionality needed. The approach is exemplified on a relatively small dynamical system, which still illustrates the complexity and possible computational gain with the proposed approach. [183] Aida Vitoria, Andrzej Szalas and Jan Maluszynski. 2008. Four-valued Extension of Rough Sets. In Proceedings of the 3rd International Conference Rough Sets and Knowledge Technology (RSKT), pages 106–114. In series: Lecture Notes in Computer Science #5009. Springer. ISBN: 978-3-540-79720-3. DOI: 10.1007/978-3-540-79721-0_19. Rough set approximations of Pawlak [15] are sometimes generalized by using similarities between objects rather than elementary sets. In practical applications, both knowledge about properties of objects and knowledge of similarity between objects can be incomplete and inconsistent. The aim of this paper is to define set approximations when all sets, and their approximations, as well as similarity relations are four-valued. A set is four-valued in the sense that its membership function can have one of the four logical values: unknown (u), false (f), inconsistent (i), or true (t). To this end, a new implication operator and set-theoretical operations on four-valued sets, such as set containment, are introduced. Several properties of lower and upper approximations of four-valued sets are also presented. [182] Jan Maluszynski, Aida Vitoria and Andrzej Szalas. 2008. Paraconsistent Logic Programs with Four-valued Rough Sets. In Proceedings of the 6th International Conference on Rough Sets and Current Trends in Computing (RSCTC). In series: Lecture Notes in Computer Science #5306. Springer. ISBN: 978-3-540-88423-1. DOI: 10.1007/978-3-540-88425-5_5. This paper presents a language for defining four-valued rough sets and to reason about them. Our framework brings together two major fields: rough sets and paraconsistent logic programming. On the one hand it provides a paraconsistent approach, based on four-valued rough sets, for integrating knowledge from different sources and reasoning in the presence of inconsistencies. On the other hand, it also caters for a specific type of uncertainty that originates from the fact that an agent may perceive different objects of the universe as being indiscernible. This paper extends the ideas presented in [9]. Our language allows the user to define similarity relations and use the approximations induced by them in the definition of other four-valued sets. A positive aspect is that it allows users to tune the level of uncertainty or the source of uncertainty that best suits applications. [181] Rickard Karlsson, Thomas Schön, David Törnqvist, Gianpaolo Conte and Fredrik Gustafsson. 2008. Utilizing Model Structure for Efficient Simultaneous Localization and Mapping for a UAV Application. In Proceedings of Reglermöte 2008, pages 313–322. Related report: http://urn.kb.se/resolve?urn=urn:nbn:se:... This contribution aims at unifying two recent trends in applied particle filtering (PF). The first trend is the major impact in simultaneous localization and mapping (SLAM) applications, utilizing the FastSLAM algorithm. Thesecond one is the implications of the marginalized particle filter (MPF) or the Rao-Blackwellized particle filter (RBPF) in positioning and tracking applications. Using the standard FastSLAM algorithm, only low-dimensional vehicle modelsare computationally feasible. In this work, an algorithm is introduced which merges FastSLAM and MPF, and the result is an algorithm for SLAM applications, where state vectors of higher dimensions can be used. Results using experimental data from a UAV (helicopter) are presented. The algorithmfuses measurements from on-board inertial sensors (accelerometer and gyro) and vision in order to solve the SLAM problem, i.e., enable navigation over a long period of time. [180] Fredrik Heintz, Mattias Krysander, Jacob Roll and Erik Frisk. 2008. FlexDx: A Reconfigurable Diagnosis Framework. In Proceedings of the 19th International Workshop on Principles of Diagnosis (DX). Detecting and isolating multiple faults is a computationally intense task which typically consists of computing a set of tests, and then computing the diagnoses based on the test results. This paper describes FlexDx, a reconfigurable diagnosis framework which reduces the computational burden by only running the tests that are currently needed. The method selects tests such that the isolation performance of the diagnostic system is maintained. Special attention is given to the practical issues introduced by a reconfigurable diagnosis framework such as FlexDx. For example, tests are added and removed dynamically, tests are partially performed on historic data, and synchronous and asynchronous processing are combined. To handle these issues FlexDx uses DyKnow, a stream-based knowledge processing middleware framework. The approach is exemplified on a relatively small dynamical system, which still illustrates the computational gain with the proposed approach. [179] 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. [178] 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 Artificial Intelligence #5325. Springer. ISBN: 978-3-540-89075-1. 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 [177] Simone Duranti and Gianpaolo Conte. 2007. In-flight Identification of the Augmented Flight Dynamics of the Rmax Unmanned Helicopter. In 17th IFAC Symposium on Automatic Control in Aerospace. International Federation of Automatic Control. DOI: 10.3182/20070625-5-FR-2916.00038. The flight dynamics of the Yamaha RMAX unmanned helicopter has been investigated, and mapped into a six degrees of freedom mathematical model. The model has been obtained by a combined black-box system identification technique and a classic model-based parameter identification approach. In particular, the closed-loop behaviour of the built-in attitude control system has been studied, to support the decision whether to keep it as inner stabilization loop or to develop an own stability augmentation system. The flight test method and the test instrumentation are described in detail; some samples of the flight test data are compared to the model outputs as validation, and an overall assessment of the built-in stabilization system is supplied. [176] Barbara Dunin-Keplicz and Andrzej Szalas. 2007. Towards Approximate BGI Systems. In Proceedings of the 5th International Central and Eastern European Conference on Multi-Agent Systems (CEEMAS), pages 277–287. In series: Lecture Notes in Artificial Intelligence #4696. Springer Berlin/Heidelberg. ISBN: 9783540752530. DOI: 10.1007/978-3-540-75254-7_28. This paper focuses on modelling perception and vague concepts in the context of multiagent Bgi (Beliefs, Goals and Intentions) systems. The starting point is the multimodal formalization of such systems. Then we make a shift from Kripke structures to similarity structures, allowing us to model perception and vagueness in an uniform way, “compatible” with the multimodal approach. As a result we introduce and discuss approximate B gi systems, which can also be viewed as a way to implement multimodal specifications of Bgi systems in the context of perception. [175] Christian Dornhege and Alexander Kleiner. 2007. Fully Autonomous Planning and Obstacle Negotiation on Rough Terrain Using Behavior Maps. In In Video Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 2561–2562. ISBN: 978-1-4244-0912-9. DOI: 10.1109/IROS.2007.4399131. To autonomously navigate on rough terrain is a challenging problem for mobile robots, requiring the ability to decide whether parts of the environment can be traversed or have to be bypassed, which is commonly known as Obstacle Negotiation (ON). In this paper, we introduce a planning framework that extends ON to the general case, where different types of terrain classes directly map to specific robot skills, such as climbing stairs and ramps. This extension is based on a new concept called behavior maps, which is utilized for the planning and execution of complex skills. Behavior maps are directly generated from elevation maps, i.e. two-dimensional grids storing in each cell the corresponding height of the terrain surface, and a set of skill descriptions. Results from extensive experiments are presented, showing that the method enables the robot to explore successfully rough terrain in real-time, while selecting the optimal trajectory in terms of costs for navigation and skill execution. [174] Holger Kenn and Alexander Kleiner. 2007. Towards the Integration of Real-Time Real-World Data in Urban Search and Rescue Simulation. In MobileResponse, pages 106–115. The coordinated reaction to a large-scale disaster is a challenging research problem. The Robocup rescue simulation league addresses this research problem but is currently lacking an interface to real-world real-time data to test the validity of both simulation and simulated reactions. In this paper, we describe a wearable-computing-based real world interface to the Robocup Resuce simulation software and provide some updated results of preliminary evaluations. [173] Christian Dornhege and Alexander Kleiner. 2007. Behavior Maps for Online Planning of Obstacle Negotiation and Climbing on Rough Terrain. In In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 3005–3011. IEEE conference proceedings. ISBN: 978-1-4244-0912-9. DOI: 10.1109/IROS.2007.4399107. To autonomously navigate on rough terrain is a challenging problem for mobile robots, requiring the ability to decide whether parts of the environment can be traversed or have to be bypassed, which is commonly known as Obstacle Negotiation (ON). In this paper, we introduce a planning framework that extends ON to the general case, where different types of terrain classes directly map to specific robot skills, such as climbing stairs and ramps. This extension is based on a new concept called behavior maps, which is utilized for the planning and execution of complex skills. Behavior maps are directly generated from elevation maps, i.e. two-dimensional grids storing in each cell the corresponding height of the terrain surface, and a set of skill descriptions. Results from extensive experiments are presented, showing that the method enables the robot to explore successfully rough terrain in real-time, while selecting the optimal trajectory in terms of costs for navigation and skill execution. [172] Alexander Kleiner, C. Dornhege and D. Sun. 2007. Mapping Disaster Areas Jointly: RFID-Coordinated SLAM by Humans and Robots. In IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR), pages 1–6. IEEE. ISBN: 978-1-4244-1569-4. DOI: 10.1109/SSRR.2007.4381263. We consider the problem of jointly performing SLAM by humans and robots in Urban Search And Rescue (USAR) scenarios. In this context, SLAM is a challenging task. First, places are hardly re-observable by vision techniques since visibility might be affected by smoke and fire. Second, loop-closure is cumbersome due to the fact that firemen will intentionally try to avoid performing loops when facing the reality of emergency response, e.g. while they are searching for victims. Furthermore, there might be places that are only accessible to robots, making it necessary to integrate humans and robots into one team for mapping the area after a disaster. In this paper, we introduce a method for jointly correcting individual trajectories of humans and robots by utilizing RFID technology for data association. Hereby the poses of humans and robots are tracked by a PDR (Pedestrian Dead Reckoning), and slippage sensitive odometry, respectively. We conducted extensive experiments with a team of humans, and a human-robot team within a semi-outdoor environment. Results from these experiments show that the introduced method allows to improve single trajectories based on the joint graph, even if they do not contain any loop. [171] Alexander Kleiner and R. Kümmerle. 2007. Genetic MRF Model Optimization for Real-Time Victim Detection in Search and Rescue. In IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 3025–3030. IEEE conference proceedings. ISBN: 978-1-4244-0912-9. DOI: 10.1109/IROS.2007.4399006. One primary goal in rescue robotics is to deploy a team of robots for coordinated victim search after a disaster. This requires robots to perform subtasks, such as victim detection, in real-time. Human detection by computationally cheap techniques, such as color thresholding, turn out to produce a large number of false-positives. Markov Random Fields (MRFs) can be utilized to combine the local evidence of multiple weak classifiers in order to improve the detection rate. However, inference in MRFs is computational expensive. In this paper we present a novel approach for the genetic optimizing of the building process of MRF models. The genetic algorithm determines offline relevant neighborhood relations with respect to the data, which are then utilized for generating efficient MRF models from video streams during runtime. Experimental results clearly show that compared to a Support Vector Machine (SVM) based classifier, the optimized MRF models significantly reduce the false-positive rate. Furthermore, the optimized models turned out to be up to five times faster then the non-optimized ones at nearly the same detection rate. [170] Alexander Kleiner and D. Sun. 2007. Decentralized SLAM for Pedestrians without direct Communication. In In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 1461–1466. IEEE conference proceedings. ISBN: 978-1-4244-0912-9. DOI: 10.1109/IROS.2007.4399013. We consider the problem of Decentralized Simultaneous Localization And Mapping (DSLAM) for pedestrians in the context of Urban Search And Rescue (USAR). In this context, DSLAM is a challenging task. First, data exchange fails due to cut off communication links. Second, loop-closure is cumbersome due to the fact that fireman will intentionally try to avoid performing loops, when facing the reality of emergency response, e.g. while they are searching for victims. In this paper, we introduce a solution to this problem based on the non-selfish sharing of information between pedestrians for loop-closure. We introduce a novel DSLAM method which is based on data exchange and association via RFID technology, not requiring any radio communication. The approach has been evaluated within both outdoor and semi-indoor environments. The presented results show that sharing information between single pedestrians allows to optimize globally their individual paths, even if they are not able to communicate directly. [169] V. A. Ziparo, Alexander Kleiner, A. Farinelli, L. Marchetti and D. Nardi. 2007. Cooperative Exploration for USAR Robots with Indirect Communication. In Proc. of 6th IFAC Symposium on Intelligent Autonomous Vehicles (IAV). To coordinate a team of robots for exploration is a challenging problem, particularly in unstructured areas, as for example post-disaster scenarios where direct communication is severely constrained. Furthermore, conventional methods of SLAM, e.g. those performing data association based on visual features, are doomed to fail due to bad visibility caused by smoke and fire. We use indirect communication (based on RFIDs), to share knowledge and use a gradient-like local search to direct robots towards interesting areas. To share a common frame of reference among robots we use a feature based SLAM approach (where features are RFIDs). The approach has been evaluated on a 3D simulation based on USARSim. [168] V. A. Ziparo, Alexander Kleiner, B. Nebel and D. Nardi. 2007. RFID-Based Exploration for Large Robot Teams. In Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pages 4606–4613. IEEE. DOI: 10.1109/ROBOT.2007.364189. To coordinate a team of robots for exploration is a challenging problem, particularly in large areas as for example the devastated area after a disaster. This problem can generally be decomposed into task assignment and multi-robot path planning. In this paper, we address both problems jointly. This is possible because we reduce significantly the size of the search space by utilizing RFID tags as coordination points. The exploration approach consists of two parts: a stand-alone distributed local search and a global monitoring process which can be used to restart the local search in more convenient locations. Our results show that the local exploration works for large robot teams, particularly if there are limited computational resources. Experiments with the global approach showed that the number of conflicts can be reduced, and that the global coordination mechanism increases significantly the explored area. [167] Karolina Eliasson. 2007. Case-Based Techniques Used for Dialogue Understanding and Planning in a Human-Robot Dialogue System. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. [166] Per Nyblom. 2007. Dynamic Planning Problem Generation in a UAV Domain. In 6th IFAC Symposium on Intelligent Autonomous Vehicles (2007) Intelligent Autonomous Vehicles, Volume# 6 | Part# 1, pages 258–263. In series: IFAC Proceedings series #??. Elsevier. ISBN: 978-3-902661-65-4. DOI: 10.3182/20070903-3-FR-2921.00045. One of the most successful methods for planning in large partially observable stochastic domains is depth-limited forward search from the current belief state together with a utility estimation. However, when the environment is continuous and the number of possible actions is practically infinite, then abstractions have to be made before any forward search planning can be performed. The paper presents a method to dynamically generate such planning problem abstractions for a domain that is inspired by our research with unmanned aerial vehicles (UAVs). The planning problems are created by first stating the selection of points to fly to as an optimization problem. When the points have been selected, a set of possible paths between them are then created with a pathplanner and then forward search in the belief state space is applied. The method has been implemented and tested in simulation and the experiments show the importance of modelling both the dynamics of the environment and the limited computational resources of the architecture when searching for suitable parameters in the planning problem formulation procedure. [165] David Lawrence, Erik Sandewall and Peter Berkesand. 2007. A Swedish Journal Publication Service. In Högskolor och samhälle i samverkan (HSS). In 2002, Linköping University Electronic Press began development of a journal article reviewing support system (JARSS) as a tool for Editors of electronic journals. The system-s database contains submitted articles, abstracts and other secondary information, reviews, and e-mail communication for the purpose of submission, reviewing and final acceptance. The interface maintains a log of all events pertaining to the article and the associated status changes. The successive status options of an article (received, under review, conditional accept, etc.) correspond to the editorial workflow. JARRS has been used since its inception to run the Artificial Intelligence Journal (AIJ), an Elsevier publication. In essence a service is offered to take care of the technical aspects of journal publication, allowing editors more time to solicit papers of high quality. [164] 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. [163] 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. [162] 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. [161] 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. [160] 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. [159] 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. [158] 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. [157] 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 [156] 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. [155] Alexander Kleiner, Nils Behrens and Holger Kenn. 2006. Wearable Computing Meets Multiagent Systems: A Real-World Interface for the RoboCupRescue Simulation Platform. In First International Workshop on Agent Technology for Disaster Management at AAMAS06, pages 116–123. One big challenge in disaster response is to get an overview over the degree of damage and to provide this information, together with optimized plans for rescue missions, back to teams in the field. Collapsing infrastructure, limited visibility due to smoke and dust, and overloaded communication lines make it nearly impossible for rescue teams to report the total situation consistently. This problem can only be solved by efficiently integrating data of many observers into a single consistent view. A Global Positioning System (GPS) device in conjunction with a communication device, and sensors or simple input methods for reporting observations, offer a realistic chance to solve the data integration problem. We propose preliminary results from a wearable computing device, acquiring disaster relevant data, such as locations of victims and blockades, and show the data integration into the RoboCupRescue Simulation platform, which is a benchmark for MAS within the RoboCup competitions. We show exemplarily how the data can consistently be integrated and how rescue missions can be optimized by solutions developed on the RoboCupRescue simulation platform. The preliminary results indicate that nowadays wearable computing technology combined with MAS technology can serve as a powerful tool for Urban Search and Rescue (USAR). [154] Christian Dornhege and Alexander Kleiner. 2006. Visual Odometry for Tracked Vehicles. In In Proc. of the IEEE Int. Workshop on Safety, Security and Rescue Robotics (SSRR). Localization and mapping on autonomous robots typically requires a good pose estimate, which is hard to acquire if the vehicle is tracked. In this paper we describe a solution to the pose estimation problem by utilizing a consumer-quality camera and an Inertial Measurement Unit (IMU). The basic idea is to continuously track salient features with the KLT feature tracker over multiple images taken by the camera and to extract from the tracked features image vectors resulting from the robot’s motion. Each image vector is taken for a voting that best explains the robot’s motion. Image vectors vote according to a previously trained tile coding classificator that assigns to each possible image vector a translation probability. Our results show that the proposed single camera solution leads to sufficiently accurate pose estimates of the tracked vehicle. [153] Alexander Kleiner, J. Prediger and Bernhard Nebel. 2006. RFID Technology-based Exploration and SLAM for Search And Rescue. In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 4054–4059. IEEE conference proceedings. ISBN: 1-4244-0258-1. DOI: 10.1109/IROS.2006.281867. Robot search and rescue is a time critical task, i.e. a large terrain has to be explored by multiple robots within a short amount of time. The efficiency of exploration depends mainly on the coordination between the robots and hence on the reliability of communication, which considerably suffers under the hostile conditions encountered after a disaster. Furthermore, rescue robots have to generate a map of the environment which has to be sufficiently accurate for reporting the locations of victims to human task forces. Basically, the robots have to solve autonomously in real-time the problem of Simultaneous Localization and Mapping (SLAM). This paper proposes a novel method for real-time exploration and SLAM based on RFID tags that are autonomously distributed in the environment. We utilized the algorithm of Lu and Milios for calculating globally consistent maps from detected RFID tags. Furthermore we show how RFID tags can be used for coordinating the exploration of multiple robots. Results from experiments conducted in the simulation and on a robot show that our approach allows the computationally efficient construction of a map within harsh environments, and coordinated exploration of a team of robots. [152] Alexander Kleiner and V. A. Ziparo. 2006. RoboCupRescue - Simulation League Team RescueRobots Freiburg (Germany). In RoboCup 2006 (CDROM Proceedings), Team Description Paper, Rescue Simulation League. Note: (1st place in the competition) This paper describes the approach of the RescueRobots Freiburg Virtual League team. Our simulated robots are based on the two real robot types Lurker, a robot capable of climbing stairs and random stepfield, and Zerg, a lightweight and agile robot, capable of autonomously distributing RFID tags. Our approach covers a novel method for RFID-Technology based SLAM and exploration, allowing the fast and efficient coordination of a team of robots. Furthermore we utilize Petri nets for team coordination. [151] Per Nyblom. 2006. Dynamic Abstraction for Hierarchical Problem Solving and Execution in Stochastic Dynamic Environments. In Loris Penserini, Pavlos Peppas, Anna Perini, editors, STAIRS 2006, pages 263–264. In series: Frontiers in Artificial Intelligence and Applications #142. IOS Press. ISBN: 978-1-58603-645-4, e-978-1-60750-190-9. Link to publication: http://www.booksonline.iospress.nl/Conte... Most of today’s autonomous problem solving agents perform their task with the help of problem domain specifications that keep their abstractions fixed. Those abstractions are often selected by human users. We think that the approach with fixed-abstraction domain specifications is very inflexible because it does not allow the agent to focus its limited computational resources on what may be most relevant at the moment. We would like to build agents that dynamically find suitable abstractions depending on relevance for their current task and situation. This idea of dynamic abstraction has recently been considered an important research problem within the area of hierarchical reinforcement learning [1]. [150] Torsten Merz, Simone Duranti and Gianpaolo Conte. 2006. Autonomous landing of an unmanned helicopter based on vision and inertial sensing. In Marcelo H. Ang and Oussama Khatib, editors, Proceedings of the 9th International Symposium on Experimental Robotics, pages 343–352. In series: Springer Tracts in Advanced Robotics #21. Springer. ISBN: 978-3-540-28816-9. DOI: 10.1007/11552246_33. Link to Ph.D. Thesis: http://urn.kb.se/resolve?urn=urn:nbn:se:... In this paper we propose an autonomous precision landing method for an unmanned helicopter based on an on-board visual navigation system consisting of a single pan-tilting camera, off-the-shelf computer hardware and inertial sensors. Compared to existing methods, the system doesn't depend on additional sensors (in particular not on GPS), offers a wide envelope of starting points for the autonomous approach, and is robust to different weather conditions. Helicopter position and attitude is estimated from images of a specially designed landing pad. We provide results from both simulations and flight tests, showing the performance of the vision system and the overall quality of the landing. © Springer-Verlag Berlin/Heidelberg 2006. [149] Andrzej Szalas and Jerzy Tyszkiewicz. 2006. On the fixpoint theory of equality and its applications. In Proceedings of the 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications of Kleene Algebra (RelMiCS/AKA), pages 388–401. In series: Lecture Notes in Computer Science #4136. Springer. DOI: 10.1007/11828563_26. In the current paper we first show that the fixpoint theory of equality is decidable. The motivation behind considering this theory is that second-order quantifier elimination techniques based on a theorem given in [16], when successful, often result in such formulas. This opens many applications, including automated theorem. proving, static verification of integrity constraints in databases as well as reasoning with weakest sufficient and strongest necessary conditions. [148] 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. [147] Anders Sandholm, Peter Bunus and Peter Fritzson. 2006. A Numeric Library for Use in Modelica Simulations with Lapack, SuperLU, Interpolation, and MatrixIO. In 5th International Modelica Conference Modelica2006,2006. [146] 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 [145] Martin Magnusson. 2006. Natural Language Understanding using Temporal Action Logic. In Proceedings of the Workshop on Knowledge and Reasoning for Language Processing (KRAQ). Association for Computational Linguistics. We consider a logicist approach to natural language understanding based on the translation of a quasi-logical form into a temporal logic, explicitly constructed for the representation of action and change, and the subsequent reasoning about this semantic structure in the context of a background knowledge theory using automated theorem proving techniques. The approach is substantiated through a proof-of-concept question answering system implementation that uses a head-driven phrase structure grammar developed in the Linguistic Knowledge Builder to construct minimal recursion semantics structures which are translated into a Temporal Action Logic where both the SNARK automated theorem prover and the Allegro Prolog logic programming environment can be used for reasoning through an interchangeable compilation into first-order logic or logic programs respectively. [144] H.Joe Steinhauer. 2006. Qualitative Reconstruction and Update of an Object Constellation. In Proceedings of the Spatial and Temporal Reasoning Workshop at the 17th European Conference on Artificial Intelligence (ECAI). We provide a technique for describing, reconstructing and updating an object constellation of moving objects. The relations between the constituent objects, in particular axis-parallel and diagonal relations, are verbally expressed using the double cross method for qualitatively characterizing relations between pairs of objects. The same underlying representation is used to reconstruct the constellation from the given description. [143] H.Joe Steinhauer. 2006. Qualitative Communication about Object Scenes. In Proceedings of the 29th Annual German Conference on Artificial Intelligence (KI). [142] 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. [141] Torsten Merz, Piotr Rudol and Mariusz Wzorek. 2006. Control System Framework for Autonomous Robots Based on Extended State Machines. In ICAS 2006 - International Conference on Autonomic and Autonomous Systems,2006. [140] 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. [139] 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. [138] 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. [137] Björn Hägglund and Anders Haraldsson. 2006. The Art and Virtue of Symbolic Constraint Propagation. In CP 2006 Twelfth International Conference on Principles and Practice of Constraint Programming,2006. [136] Mikhail Chalabine, Christoph Kessler and Peter Bunus. 2006. Automated Round-trip Software Engineering in Aspect Weaving Systems. In 21st IEEE/ACM International Conference on Automated Software Engineering, 2006. ASE '06., pages 305–308. In series: IEEE / ACM International Conference on Automated Software Engineering #??. IEEE/ACM. ISBN: 0-7695-2579-2. DOI: 10.1109/ASE.2006.20. We suggest an approach to Automated Round-trip Software Engineering in source-level aspect weaving systems that allows for transparent mapping of manual edits in the woven program back to the appropriate source of origin, which is either the application core or the aspect space. [135] Ewa Orlowska and Andrzej Szalas. 2006. Quantifier Elimination in Elementary Set Theory. In W. MacCaull, I. Duentsch, M. Winter, editors, Proceedings of the 8th International Conference on Relational Methods in Computer Science (RelMiCS), pages 237–248. In series: Lecture Notes in Computer Science #3929. Springer Berlin/Heidelberg. DOI: 10.1007/11734673_19. In the current paper we provide two methods for quantifier elimination applicable to a large class of formulas of the elementary set theory. The first one adapts the Ackermann method [1] and the second one adapts the fixpoint method of [20]. We show applications of the proposed techniques in the theory of correspondence between modal logics and elementary set theory. The proposed techniques can also be applied in an automated generation of proof rules based on the semantic-based translation of axioms of a given logic into the elementary set theory. 2005 [134] Alexander Kleiner, Michael Brenner, Tobias Bräuer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger, Jörg Stückler and Bernhard Nebel. 2005. Successful Search and Rescue in Simulated Disaster Areas. In Robocup 2005: Robot Soccer World Cup IX, pages 323–334. RoboCupRescue Simulation is a large-scale multi-agent simulation of urban disasters where, in order to save lives and minimize damage, rescue teams must effectively cooperate despite sensing and communication limitations. This paper presents the comprehensive search and rescue approach of the ResQ Freiburg team, the winner in the RoboCupRescue Simulation league at RoboCup 2004. Specific contributions include the predictions of travel costs and civilian life-time, the efficient coordination of an active disaster space exploration, as well as an any-time rescue sequence optimization based on a genetic algorithm. We compare the performances of our team and others in terms of their capability of extinguishing fires, freeing roads from debris, disaster space exploration, and civilian rescue. The evaluation is carried out with information extracted from simulation log files gathered during RoboCup 2004. Our results clearly explain the success of our team, and also confirm the scientific approaches proposed in this paper. [133] T. A. Nüssle, Alexander Kleiner and M. Brenner. 2005. Approaching Urban Disaster Reality: The ResQ Firesimulator. In RoboCup 2004: Robot Soccer World Cup VIII, pages 474–482. In series: Lecture Notes in Computer Science #3276/2005. DOI: 10.1007/978-3-540-32256-6_42. The RoboCupRescue Simulation project aims at simulating large-scale disasters in order to explore coordination strategies for real-life rescue missions. This can only be achieved if the simulation itself is as close to reality as possible. In this paper, we present a new fire simulator based on a realistic physical model of heat development and heat transport in urban fires. It allows to simulate three different ways of heat transport (radiation, convection, direct transport) and the influence of wind. The protective effects of spraying water on non-burning buildings is also simulated, thus allowing for more strategic and precautionary behavior of rescue agents. Our experiments showed the simulator to create realistic fire propagations both with and without influence of fire brigade agents. [132] Alexander Kleiner, B. Steder, C. Dornhege, D. Höfer, D. Meyer-Delius, J. Prediger, J. Stückler, K. Glogowski, M. Thurner, M. Luber, M. Schnell, R. Kuemmerle, T. Burk, T. Bräuer and B. Nebel. 2005. RoboCupRescue - Robot League Team RescueRobots Freiburg (Germany). In RoboCup 2005 (CDROM Proceedings), Team Description Paper, Rescue Robot League. Note: (1st place in the autonomy competition, 4th place in the teleoperation competition) This paper describes the approach of the RescueRobots Freiburg team. RescueRobots Freiburg 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). Due to the high versatility of the RoboCupRescue competition we tackle the three arenas by a a twofold approach: On the one hand we want to introduce robust vehicles that can safely be teleoperated through rubble and building debris while constructing three-dimensional maps of the environment. On the other hand we want to introduce a team of autonomous robots that quickly explore a large terrain while building a two-dimensional map. This two solutions are particularly well-suited for the red and yellow arena, respectively. Our solution for the orange arena will finally be decided between these two, depending on the capabilities of both approaches at the venue. In this paper, we introduce some preliminary results that we achieved so far from map building, localization, 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. [131] Peter Andersson. 2005. Hazard: a Framework Towards Connecting Artificial Intelligence and Robotics. In IJCAI Workshop on Reasoning, Representation and Learning in Computer Games. [130] Ewa Madalinska-Bugaj and Witold Lukaszewicz. 2005. Belief revision revisited. In Advances in Artificial Intelligence: Proceedings of the 4th Mexican International Conference on Artificial Intelligence (MICAI), pages 31–40. In series: Lecture Notes in Computer Science #3789. Springer. DOI: 10.1007/11579427_4. In this paper, we propose a new belief revision operator, together with a method of its calculation. Our formalization differs from most of the traditional approaches in two respects. Firstly, we formally distinguish between defeasible observations and indefeasible knowledge about the considered world. In particular, our operator is differently specified depending on whether an input formula is an observation or a piece of knowledge. Secondly, we assume that a new observation, but not a new piece of knowledge, describes exactly what a reasoning agent knows at the moment about the aspect of the world the observation concerns. [129] 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. [128] 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. [127] Michali Grabowski and Andrzej Szalas. 2005. A Technique for Learning Similarities on Complex Structures with Applications to Extracting Ontologies. In Proceedings of the 3rd Atlantic Web Intelligence Conference (AWIC), pages 991–995. In series: Lecture Notes in Computer Science #3528. Springer. DOI: 10.1007/11495772_29. A general similarity-based algorithm for extracting ontologies from data has been provided in [1]. The algorithm works over arbitrary approximation spaces, modeling notions of similarity and mereological part-of relations (see, e.g., [2, 3, 4, 5]). In the current paper we propose a novel technique of machine learning similarity on tuples on the basis of similarities on attribute domains. The technique reflects intuitions behind tolerance spaces of [6] and similarity spaces of [7]. We illustrate the use of the technique in extracting ontologies from data. [126] Erik Johan Sandewall. 2005. Actions as a Basic Software Concept in the Leonardo Computation System. In IJCAI 2005 Workshop on Nonmonotonic Reasoning, Action and Change,2005. [125] Erik Johan Sandewall. 2005. Integration of Live Video in a System for Natural Language Dialog with a Robot. In Proceedings of the 9th workshop on the semantics and pragmatics of dialogue (SemDial). [124] 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. [123] 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). [122] 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. [121] Patrik Haslum, Blai Bonet and Hector Geffner. 2005. New Admissible Heuristics for Domain-Independent Planning. In Proceedings of the 20th national ´Conference on Artificial Intelligence (AAAI). AAAI Press. ISBN: 1-57735-236-X. Admissible heuristics are critical for effective domain-independent planning when optimal solutions must be guaranteed. Two useful heuristics are the hm heuristics, which generalize the reachability heuristic underlying the planning graph, and pattern database heuristics. These heuristics, however, have serious limitations: reachability heuristics capture only the cost of critical paths in a relaxed problem, ignoring the cost of other relevant paths, while PDB heuristics, additive or not, cannot accommodate too many variables in patterns, and methods for automatically selecting patterns that produce good estimates are not known.We introduce two refinements of these heuristics: First, the additive hm heuristic which yields an admissible sum of hm heuristics using a partitioning of the set of actions. Second, the constrained PDB heuristic which uses constraints from the original problem to strengthen the lower bounds obtained from abstractions.The new heuristics depend on the way the actions or problem variables are partitioned. We advance methods for automatically deriving additive hm and PDB heuristics from STRIPS encodings. Evaluation shows improvement over existing heuristics in several domains, although, not surprisingly, no heuristic dominates all the others over all domains. [120] 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. [119] 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. [118] Peter Andersson. 2005. Hazard: A Framework Towards Connecting Artificial Intelligence and Robotics. In Proceedings of the 1st International Workshop on Multi-Agent Robotic Systems (MARS). INSTICC PRESS. [117] Per Nyblom. 2005. Handling Uncertainty by Interleaving Cost-Aware Classical Planning with Execution. In 3rd joint SAIS-SSL event on Artificial Intelligence and Learning Systems,2005. [116] 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. [115] 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. [114] Karolina Eliasson. 2005. Towards a Robotic Dialogue System with Learning and Planning Capabilities. In Ingrid Zukerman, Jan Alexandersson , Arne Jönsson, editors, Proceedings of the IJCAI Workshop on Knowledge and Reasoning in Practical Dialogue Systems (KRPDS), pages 1–7. We present a robotic dialogue system built on casebased reasoning. The system is capable of solving references and manage sub-dialogues in a dialogue with an operator in natural language. The approach to handle dialogue acts and physical acts in a unison manner together with the use of plans and subplans makes the system very flexible. This flexibility is used for learning purposes where the operator teaches the system a new word and the new knowledge can directly be integrated and used in the old plans. The learning from explanation capability makes the system adaptable to the operator's use of language and the domain it is currently operating in. The implementation of a case-based planner suggested in the paper will further increase the learning and adaptation degree. [113] Karolina Eliasson. 2005. Integrating a Discourse Model with a Learning Case-Based Reasoning System. In Proceedings of the 9th workshop on the semantics and pragmatics of dialogue (SemDial). We present a discourse model integrated with a case-based reasoning dialogue system which learns from experience. The discourse model is capable of solving references, manage subdialogues and respect the current topic in a dialogue in natural language. The framework is flexible enough not to disturb the learning functions, but allows dynamic changes to a large extent. The system is tested in a traffic surveillance domain together with a simulated UAV and is found to be robust and reliable. [112] Karolina Eliasson. 2005. An Integrated Discourse Model for a Case-Based Reasoning Dialogue System. In 3rd joint SAIS-SSL event on Artificial Intelligence and Learning Systems,2005. [111] H.Joe Steinhauer. 2005. Towards a Qualitative Model for Natural Language Communication about Vehicle Traffic. In IJCAI 2005 Workshop on Spatial and Temporal Reasoning,2005. [110] H.Joe Steinhauer. 2005. A Qualitative Model for Natural Language Communication about Vehicle Traffic. In Proceedings of the AAAI Spring Symposium on Reasoning with Mental and External Diagrams - Computational Modeling and Spatial Assistance, pages 52–57. AAAI Press. ISBN: 978-1-57735-232-7. In this paper we describe a qualitative approach for natural language communication about vehicle traffic. It is an intuitive and simple model that can be used as the basis for defining more detailed position descriptions and transitions. It can also function as a framework for relating different aggregation levels. We apply a diagrammatic abstraction of traffic that mirrors the different possible interpretations of it and with this the different mental abstractions that humans might make. The abstractions are kept in parallel and according to the communicative context it will be switched to the corresponding interpretation. [109] Peter Bunus. 2005. An Empirical Study on Debugging Equation-based Simulation Models. In 4th International Modelica Conference,2005. Link: http://www.modelica.org 2004 [108] Alexander Kleiner, Michael Brenner, Tobias Bräuer, Christian Dornhege, Moritz Göbelbecker, Matthias Luber, Johann Prediger and Joerg Stückler. 2004. ResQ Freiburg: Team Description and Evaluation. In RoboCup 2004 (CDROM Proceedings), Team Description Paper, Rescue Simulation League. Note: (1st place in the competition) ResQ Freiburg is the world champion of the 2004 RoboCup competition in the Rescue simulation league. RoboCupRescue is a large-scale multi-agent simulation of urban disasters where, in order to save lives and minimize damage, rescue teams must effectively cooperate despite sensing and communication limitations. To accomplish this, ResQ Freiburg introduced new methods for hierarchical path planning, death-time prediction of civilians, coordination of multi-agent city exploration, as well as an any-time rescue sequence optimization based on genetic algorithms. To evaluate the usefulness of these techniques we performed an extensive evaluation of the log files of the best participating teams in the competition. Our analysis explains the reasons for our team’s success, and thus could also provide an evaluation tool for future competitions. [107] 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. [106] Patrik Haslum. 2004. Patterns in Reactive Programs. In Patrick Doherty, Gerhard Lakemeyer, Angel P. de Pobil, editors, Proceedings of the 4th International Cognitive Robotics Workshop (COGROB), pages 25–29. In this paper, I explore the idea that there are “patterns”,analogous to software design patterns, in the kind of task proceduresthat frequently form the reactive component of architectures for intelligentautonomous systems. The investigation is carried out mainlywithin the context of the WITAS UAV project. [105] 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. [104] Håkan Lundvall, Peter Bunus and Peter Fritzson. 2004. Towards Automatic Generation of Model Checkable Code from Modelica. In SIMS 2004, the 45th Conference on Simulation and Modelling. September 2004,2004. [103] Peter Fritzson, Vadim Engelson, Andreas Idebrant, Peter Aronsson, Håkan Lundvall, Peter Bunus and Kaj Nyström. 2004. Modelica - A Strongly Typed System Specification Language for Safe Engineering Practices. In SIMSAFE2004,2004. [102] Bourhane Kadmiry and P Bergsten. 2004. Robust Fuzzy Gain Scheduled visual-servoing with Sampling Time Uncertainties. In IEEE International Symposium on Intelligent Control ISIC,2004. Abstract-This paper addresses the robust fuzzy control problem for discrete-time nonlinear systems in the presence of sampling time uncertainties in a visual-servoing control scheme. The Takagi-Sugeno (T-S) fuzzy model is adopted for the nonlinear geometric model of a pin-hole camera, which presents second-order nonlinearities. The case of the discrete T-S fuzzy system with sampling-time uncertainty is considered and a multi-objective robust fuzzy controller design is proposed for the uncertain fuzzy system. The sufficient conditions are formulated in the form of linear matrix inequalities (LMI). The effectiveness of the proposed controller design methodology is demonstrated through numerical simulation, then tested on a EVI-D31 SONY camera. [101] Bourhane Kadmiry and Dimiter Driankov. 2004. Takagi-Sugeno Fuzzy Gain Scheduling with Sampling-Time Uncertainties. In IEEE International Conference on Fuzzy Systems Fuzz-IEEE 2004,2004. This paper addresses the robust fuzzy control problem for discrete-time nonlinear systems in the presence of sampling time uncertainties. The case of the discrete T-S fuzzy system with sampling-time uncertainty is considered and a robust controller design method is proposed. The sufficient conditions and the design procedure are formulated in the form of linear matrix inequalities (LMI). The effectiveness of the proposed controller design methodology is demonstrated of a visual-servoing control problem [100] 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. [99] 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. [98] H.Joe Steinhauer. 2004. The Qualitative Description of Traffic Maneuvers. In ECAI Workshop on Spatial and Temporal Reasoning,2004, pages 141–148. [97] 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. [96] 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. [95] 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. [94] Torsten Merz. 2004. Building a System for Autonomous Aerial Robotics Research. In Proceedings of the 5th IFAC Symposium on Intelligent Autonomous Vehicles (IAV). Elsevier. ISBN: 008-044237-4. [93] Gianpaolo Conte, Simone Duranti and Torsten Merz. 2004. Dynamic 3D path following for an autonomous helicopter. In Proceedings of the 5th IFAC Symposium on Intelligent Autonomous Vehicles (IAV). Elsevier. ISBN: 008-044237-4. Link to Licentiate Thesis: http://urn.kb.se/resolve?urn=urn:nbn:se:... A hybrid control system for dynamic path following for an autonomous helicopter is described. The hierarchically structured system combines continuous control law execution with event-driven state machines. Trajectories are defined by a sequence of 3D path segments and velocity profiles, where each path segment is described as a parametric curve. The method can be used in combination with a path planner for flying collision-free in a known environment. Experimental flight test results are shown. [92] 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. [91] 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. [90] 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. [89] 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. [88] Patrik Haslum. 2004. Improving Heuristics Through Search. In Ramon López de Mántaras, Lorenza Saitta, editors, Proceedings of the 16th Eureopean Conference on Artificial Intelligence (ECAI), pages 1031–1032. IOS Press. ISBN: 1-58603-452-9. We investigate two methods of using limited search to improve admissible heuristics for planning, similar to pattern databases and pattern searches. We also develop a new algorithm for searching AND/OR graphs 2003 [87] Alexander Kleiner and T. Buchheim. 2003. A Plugin-Based Architecture for Simulation in the F2000 League. In In RoboCup 2003: Robot Soccer World Cup VII, pages 434–445. Simulation has become an essential part in the development process of autonomous robotic systems. In the domain of robotics, developers often are confronted with problems like noisy sensor data, hardware malfunctions and scarce or temporarily inoperable hardware resources. A solution to most of the problems can be given by tools which allow the simulation of the application scenario in varying degrees of abstraction and the suppression of unwanted features of the domain (like e.g. sensor noise). The RoboCup scenario of autonomous mobile robots playing soccer is one such domain where the above mentioned problems typically arise. [86] E. Schulenburg, T. Weigel and Alexander Kleiner. 2003. Self-Localization in Dynamic Environments based on Laser and Vision Data. In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pages 998–1004. IEEE. ISBN: 0-7803-7860-1. DOI: 10.1109/IROS.2003.1250758. For a robot situated in a dynamic real world environment the knowledge of its position and orientation is very advantageous and sometimes essential for carrying out a given task. Particularly, one would appreciate a robust, accurate and efficient selflocalization method which allows a global localization of the robot. In certain polygonal environments a laser based localization method is capable of combining all these properties by correlating observed lines with an a priori line model of the environment [5] . However, often line features can rather be detected by a vision system than by a laser range finder. For this reason we propose an extension of the laser based approach for the simultaneous use with lines detected by an omni-directional camera. The approach is evaluated in the RoboCup domain and experimental evidence is given for its robustness, accuracy and efficiency, as well as for its capability of global localization. [85] Peter Aronsson, Peter Fritzson, Levon Saldamli, Peter Bunus and Kaj Nyström. 2003. Meta Programming and Function Overloading in OpenModelica. In Proceedings of the 3rd International Modelica Conference (November 3-4, Linköping, Sweden). [84] Eva-Lena Lengquist Sandelin, Susanna Monemar, Peter Fritzson and Peter Bunus. 2003. DrModelica - A Web-Based Teaching Environment for Modelica. In Proceedings of the 44th Conference on Simulation and Modeling (SIMS). Malardalen University. ISBN: 91-631-4716-5. This paper states the need for interactive teaching materials for programming languages within the area of modeling and simulation. We propose an interactive teaching material for the modeling language Modelica inspired by existing tutoring systems for Java and Scheme.The purpose of this new teaching material, called DrModelica, is to facilitate the learning of Modelica in a modeling and simulation environment. We have developed two versions of DrModelica, one that is based on Mathematica and another that is intended for the web. With the web version of DrModelica we hope for an increased usage of Modelica. [83] Peter Bunus and Peter Fritzson. 2003. Semi-automatic Fault Localization and Behaviour Verification for Physical System Simulation Models. In In Proceedings 8th IEEE International Conference on Automated Software Engineering. (Montreal, Canada, October 6-10, 2003). [82] Vadim Engelson, Peter Bunus, Lucian Popescu and Peter Fritzson. 2003. Mechanical CAD with Multibody Dynamic Analysis Based on Modelica Simulation. In SIMS 2003 - 44th Conference on Simulation and Modeling on September 18 -19, 2003 in Västerås. [81] Eva-Lena Lengquist Sandelin, Susanna Monemar, Peter Fritzson and Peter Bunus. 2003. DrModelica - An Interactive Tutoring Environment for Modelica. In Proceedings of the 3rd International Modelica Conference. Modelica Association. This paper states the need for interactive teaching materials for programming languages within the area of modeling and simulation. We propose an interactive teaching material for the modeling language Modelica inspired by existing tutoring systems for Java and Scheme.The purpose of this new teaching material, called DrModelica, is to facilitate the learning of Modelica through an environment that integrates programming, program documentation and visualization. The teaching material is intended to be used for modeling and simulation related courses at the undergraduate and graduate level. [80] 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. [79] Andrzej Szalas. 2003. On a logical approach to estimating computational complexity of potentially intractable problems. In G. Goos, J. Hartmanis, and J. van Leeuwen, editors, Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT), pages 423–431. In series: Lecture Notes in Computer Science #2751. Springer. DOI: 10.1007/978-3-540-45077-1_39. In the paper we present a purely logical approach to estimating computational complexity of potentially intractable problems. The approach is based on descriptive complexity and second-order quantifier elimination techniques. We illustrate the approach on the case of the transversal hypergraph problem, TRANSHYP, which has attracted a great deal of attention. The complexity of the problem remains unsolved for over twenty years. Given two hypergraphs, G and H, TRANSHYP depends on checking whether G = H-d, where H-d is the transversal hypergraph of H. In the paper we provide a logical characterization of minimal transversals of a given hypergraph and prove that checking whether G subset of or equal to H-d is tractable. For the opposite inclusion the Problem still remains open. However, we interpret the resulting quantifier sequences in terms of determinism and bounded nondeterminism. The results give better upper bounds than those known from the literature, e.g., in the case when hypergraph H, has a sub-logarithmic number of hyperedges and (for the deterministic case) all hyperedges have the cardinality bounded by a function sub-linear wrt maximum of sizes of G and H. [78] 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. [77] Igor S. Pandzic, Jörgen Ahlberg, Mariusz Wzorek, Piotr Rudol and Miran Mosmondor. 2003. Faces Everywhere: Towards Ubiquitous Production and Delivery of Face Animation. In Proceedings of the 2nd International Conference on Mobile and Ubiquitous Multimedia (MUM), pages 49–56. In series: Linköping Electronic Conference Proceedings #11. Linköping University Electronic Press. Link: http://www.ep.liu.se/ecp/011/010/ecp0110... While face animation is still considered one of the toughesttasks in computer animation, its potential application range israpidly moving from the classical field of film production intogames, communications, news delivery and commerce. Tosupport such novel applications, it is important to enableproduction and delivery of face animation on a wide range ofplatforms, from high-end animation systems to the web, gameconsoles and mobile phones. Our goal is to offer a frameworkof tools interconnected by standard formats and protocols andcapable of supporting any imaginable application involvingface animation with the desired level of animation quality,automatic production wherever it is possible, and delivery ona wide range of platforms. While this is clearly an ongoingtask, we present the current state of development along withseveral case studies showing that a wide range of applicationsis already enabled. [76] Erik Johan Sandewall. 2003. High-level design of WWW servers in Allegro Common Lisp. In Proceedings of the International Lisp Conference (ILC). When invoking a function or a procedure in an ordinary programming language, it is normally assumed that the arguments may be given as composite expressions, and that they are not restricted to atomic constants or variable symbols. However, although active web pages in HTML-based web servers can be viewed as a kind of procedures, they do not enjoy the same flexibility. The present paper reports on a software package that extends the embedded web server in the ACL (Allegro Common Lisp) system and that provides it with the kind of functional flavor just described. In passing, the software also adds a number of other convenience measures to the LHTML (Lisp-encoded HTML) of the ACL server. [75] Erik Johan Sandewall. 2003. A software architecture for AI systems based on self-modifying software individuals. In Proceedings of the International Lisp Conference (ILC). The Software Individuals Architecture (SIA) is a framework fordefining software systems that are capable of self-modification and of reproductionon the level of an interpretive programming language. In abstractterms, a self-modifying system is a labelled tree containing scripts at someof its nodes; these scripts are effectively programs. A computation in sucha system executes a specific script. In doing so it maintains a local computationalstate, but it also uses and updates the labelled tree. The labelledtree, the local computational state, and the command language used for thescripts are all designed in such a way as to support self-modification andreproduction in a structured and orderly fashion.We have defined a practical system of this kind both on an abstract andformal level and as an implementation using Lisp as the host language. Thisarchitecture has been used as a platform for several applications, including inparticular the speech and natural-language dialogue system for an intelligentautonomous unmanned aerial vehicle (UAV) in the WITAS project. Thearchitecture design has been revised repeatedly as a result of using it for thisapplication as well as several others. [74] 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. [73] 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. [72] Patrik Haslum and Ulrich Scholz. 2003. Domain Knowledge in Planning: Representation and Use. In Proceedings of the ICAPS workshop on PDDL, pages 69–78. Planning systems rely on knowledge about the problems they have to solve: The problem description and in many cases advice on how to find a solution. This paper is concerned with a third kind of knowledge which we term domain knowledge: Information about the problem that is produced by one component of the planner and used for advice by another. We first distinguish domain knowledge from the problem description and from advice, and argue for the advantages of the explict use of domain knowledge. Then we identify three classes of domain knowledge for which these advantages are most apparent and define a language, DKEL, to represent these classes. DKEL is designed as an extension to PDDL. 2002 [71] Alexander Kleiner, M. Dietl and Bernhard Nebel. 2002. Towards a Life-Long Learning Soccer Agent. In In RoboCup 2002: Robot Soccer World Cup VI, pages 126–134. One problem in robotic soccer (and in robotics in general) is to adapt skills and the overall behavior to a changing environment and to hardware improvements. We applied hierarchical reinforcement learning in an SMDP framework learning on all levels simultaneously. As our experiments show, learning simultaneously on the skill level and on the skill selection level is advantageous since it allows for a smooth adaption to a changing environment. Furthermore, the skills we trained turn also out to be quite competitive when run on the real robotic players of the players of our CS Freiburg team. [70] Levon Saldamli, Peter Fritzson, Peter Aronsson, Peter Bunus, Vadim Engelson, Henrik Johansson and Andreas Karström. 2002. The Open Source Modelica Project. In Proceedings of the 2nd International Modelica Conference. Modelica Association. Note: Oberpfaffenhofen, Germany, March 18-19, 2002 [69] Peter Aronsson, Peter Fritzson, Levon Saldamli and Peter Bunus. 2002. Incremental declaration handling in Open Source Modelica. In Scandinavian Simulation Conference (SIMS), September 2002, Oulu, Finland.. [68] Patrik Haslum. 2002. Partial State Progression: An Extension to the Bacchus-Kabanza Algorithm, with Applications to Prediction and MITL Consistency. In Proceedings of the AIPS 2002 workshop on Planning via Model Checking. [67] Jonas Kvarnström. 2002. Applying Domain Analysis Techniques for Domain-Dependent Control in TALplanner. In Malik Ghallab, Joachim Hertzberg, and Paolo Traverso, editors, Proceedings of the 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS). AAAI Press. ISBN: 0-57735-142-8. DOI: 10.3233/978-1-60750-606-5-341. A number of current planners make use of automatic domain analysis techniques to extract information such as state invariants or necessary goal orderings from a planning domain. There are also planners that allow the user to explicitly specify additional information intended to improve performance. One such planner is TALplanner, which allows the use of domain-dependent temporal control formulas for pruning a forward-chaining search tree. This leads to the question of how these two approaches can be combined. In this paper we show how to make use of automatically generated state invariants to improve the performance of testing control formulas. We also develop a new technique for analyzing control rules relative to control formulas and show how this often allows the planner to automatically strengthen the preconditions of the operators, thereby reducing time complexity and improving the performance of TALplanner by a factor of up to 400 for the largest problems from the AIPS-2000 competition. [66] Erik Skarman and AB Saab. 2002. EEG waves as chaotic self-oscillations. In International Journal of Psychophysiology, pages 138–138. [65] Erik Johan Sandewall. 2002. Use of cognitive robotics logic in a double helix architecture for autonomous systems. In Advances in Plan-Based Control of Robotic Agents: Revised Papers from the International Seminar at Dagstuhl Castle, pages 226–248. In series: Lecture Notes in Computer Science #2466. Springer. DOI: 10.1007/3-540-37724-7_14. This paper addresses the two-way relation between the architecture for cognitive robots on one hand, and a logic of action and change that is adapted to the needs of such robots on the other hand. The relation goes both ways: the logic is used within the architecture, but we also propose that an abstract model of the cognitive robot architecture shall be used for defining the semantics of the logic. For this purpose, we describe a novel architecture called the Double Helix Architecture which, unlike earlier proposals, emphasizes a precise account of the metric discrete timeline and the computational processes that take place along that timeline. The computational model of the Double Helix Architecture corresponds to the semantics of the logic being used, namely the author's Cognitive Robotics Logic which is based on the 'Features and Fluents' theory. [64] Andrzej Szalas. 2002. Second-order quantifier elimination in modal contexts. In Sergio Flesca, Sergio Greco, Nicola Leone, Giovambattista Ianni, editors, Proceedings of the 8th European Conference on Logics in Artificial Intelligence (JELIA), pages 223–232. In series: Lecture Notes in Computer Science #2424. Springer. ISBN: 978-354044190-8. DOI: 10.1007/3-540-45757-7_19. Second-order quantifier elimination in the context of classical logic emerged as a powerful technique in many applications, including the correspondence theory, relational databases, deductive and knowledge databases, knowledge representation, commonsense reasoning and approximate reasoning. In the current paper we generalize the result of [19] by allowing modal operators. This allows us to provide a unifying framework for many applications, that require the use of intensional concepts. Examples of applications of the technique in AI are also provided. [63] 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. [62] 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. [...] [61] 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 [60] Lars Karlsson. 2001. Conditional Progressive Planning: A Preliminary Report. In Proceedings of the Scandinavian Conference on Artificial Intelligence (SCAI), pages 90–100. In series: Frontiers in Artificial Intelligence and Applications #66. IOS Press. [59] T. Weigel, Alexander Kleiner, F. Diesch, M. Dietl, J. -S Gutmann, B. Nebel, P. Stiegeler and B. Szerbakowski. 2001. CS Freiburg 2001. In RoboCup 2001 : Robot Soccer World Cup V, pages 26–38. The CS Freiburg team has become F2000 champion the third time in the history of RoboCup. The success of our team can probably be attributed to its robust sensor interpretation and its team play. In this paper, we will focus on new developments in our vision system, in our path planner, and in the cooperation component. [58] Joakim Gustafsson. 2001. Object-oriented Reasoning about Action and Change. In H.H. Lund, B. Mayoh, J. Perram, editors, Proceedings of the Seventh Scandinavian Conference on Artificial Intelligence (SCAI), pages 53–64. In series: Frontiers in Artificial Intelligence and Applications #66. IOS Press. ISBN: 1-58603-161-9. As the scope of logics of action and change continues to increase and powerful research tools are developed, it becomes possible to model larger and more complex scenarios. Unfortunately the scenarios become harder to read and difficult to modify and debug with increasing size and complexity. These problems have been overlooked in the action and change community due to the fact that only smaller toy problems are considered. Sound modeling methodology is as essential as the primitives of the modeling language. The object-oriented paradigm is one structuring mechanism that alleviates these problems and provides a systematic means of scenario construction. The topic of this paper is to demonstrate how many ideas from the object orientation paradigm can be used when reasoning about action and change, we show this by integrating the technique directly in an existing logic of action and change without any modification to the underlying logical language or semantics. 1 [57] Bourhane Kadmiry, Rainer Palm and Dimiter Driankov. 2001. Autonomous Helicopter Control Using Gradient Descent Optimization Method. In Proceedings of the Asian Conference on Robotic & Automation (ACRA). [56] Bourhane Kadmiry, Pontus Bergsten and Dimiter Driankov. 2001. Autonomous Helicopter Control Using Fuzzy-Gain Scheduling. In Proceedings of the IEEE International Conference on Robotic & Automation (ICRA), pages 2980–2985. IEEE conference proceedings. ISBN: 0-7803-6576-3. DOI: 10.1109/ROBOT.2001.933074. The work reported in the paper is aimed at achieving aggressive manoeuvrability for an unmanned helicopter APID MK-III by Scandicraft AB in Sweden. The manoeuvrability problem is treated at the level of attitude (pitch, roll, yaw) and the aim is to achieve stabilization of the attitude angles within much larger ranges than currently available. We present a fuzzy gain scheduling control approach based on two different types of Iinearization of the original nonlinear APID MK-III model. The performance of the fuzzy gain scheduled controllers is evaluated in simulation and shows that they are effective means for achieving the desired robust manoeuvrability. [55] Bourhane Kadmiry and Dimiter Driankov. 2001. Fuzzy Control of an Autonomous Helicopter. In Proceedings of the 9th IEEE International Fuzzy Systems Association (IFSA) World Congress, pages 2797–2802. IEEE Computer Society. ISBN: 0-7803-7078-3. DOI: 10.1109/NAFIPS.2001.943669. This work presents a horizontal velocity controller for the unmanned helicopter APID MK-III developed by Scandicraft AB in Sweden. We use a novel approach to the design consisting of two steps: 1) Mamdani-type of fuzzy rules to compute each of the desired horizontal velocity corresponding to the desired values for the attitude angles and the main rotor collective pitch; and 2) a Takagi-Sugeno controller is used to regulate the attitude angles so that the helicopter achieves its desired horizontal velocities at a desired altitude. The performance of the combined linguistic/model-based controller is evaluated in simulation and shows that the proposed design method achieves its intended purpose [54] Bourhane Kadmiry and Dimiter Driankov. 2001. Autonomous Helicopter Control using Linguistic and Model-Based Fuzzy Control. In Proceedings of the IEEE International Symposium on Intelligent Control (CCA/ISIC), pages 348–352. ISBN: 0-7803-6722-7. DOI: 10.1109/ISIC.2001.971534. The paper presents the design of a horizontal velocity controller for the unmanned helicopter APID MK-III developed by Scandicraft AB in Sweden. The controller is able of regulating high horizontal velocities via stabilization of the attitude angles within much larger ranges than currently available. We use a novel approach to the design consisting of two steps: 1) a Mamdani-type of a fuzzy rules are used to compute for each desired horizontal velocity the corresponding desired values for the attitude angles and the main rotor collective pitch; and 2) using a nonlinear model of the altitude and attitude dynamics, a Takagi-Sugeno controller is used to regulate the attitude angles so that the helicopter achieves its desired horizontal velocities at a desired altitude. According to our knowledge this is the first time when a combination of linguistic and model-based fuzzy control is used for the control of a complicated plant such as an autonomous helicopter. The performance of the combined linguistic/model-based controllers is evaluated in simulation and shows that the proposed design method achieves its intended purpose [53] Fredrik Heintz, Johan Kummeneje and Paul Scerri. 2001. Using Simulated RoboCup to Teach AI in Undergraduate Education. In Proceedings of the 7th Scandinavian Conference on Artificial Intelligence (SCAI), pages 13–21. In series: Frontiers in Artificial Intelligence and Applications #66. IOS Press. ISBN: 1-58603-161-9. In this paper we argue that RoboCup is a useful tool for the teaching of AI in undergraduate education. We provide case studies, from two Swedish universities, of how RoboCup based AI courses can be implemented using a problem based approach. Although the courses were successful there are significant areas for improvement. Firstly, to help students cope with the complexity of the domain we developed RoboSoc, a general software framework for developing simulated RoboCup agents. Secondly, we propose creating close co-operation between the teachers and researchers at Scandinavian Universities with the aim of increasing the motivation of both students and teachers by providing accessible information and competence. [52] Fredrik Heintz and Patrick Doherty. 2001. Chronicle Recognition in the WITAS UAV Project: A Preliminary Report. In Proceedings of the Swedish AI Society Workshop. [51] Patrik Haslum. 2001. Models for Prediction. In Proceedings of the IJCAI 2001 workshop on Planning under Uncertainty and Incomplete Information (PRO-2). Prediction is found to be a part of many more complex reasoning problems, e.g. state estimation, planning and diagnosis. In spite of this, the prediction problem is rarely studied on its own. Yet there appears to be a wide range of choices for the design of the central component in a solution to this problem, the predictive model. We examine some of the alternatives and, as a case study, present two different solutions to a specific prediction problem that we have encountered in the WITAS UAV project. [50] Patrik Haslum and Héctor Geffner. 2001. Heuristic Planning with Time and Resources. In Proceedings of the 6th European Conference on Planning (ECP). We present an algorithm for planning with time and resources based on heuristic search. The algorithm minimizes makespan using an admissible heuristic derived automatically from the problem instance. Estimators for resource consumption are derived in the same way. The goals are twofold: to show the flexibility of the heuristic search approach to planning and to develop a planner that combines expressivity and performance. Two main issues are the definition of regression in a temporal setting and the definition of the heuristic estimating completion time. A number of experiments are presented for assessing the performance of the resulting planner. [49] Joakim Gustafsson and Jonas Kvarnström. 2001. Elaboration Tolerance through Object-Orientation. In Proceedings of the 5th Symposium on Logical Formalizations of Commonsense Reasoning (CommonSense). Although many formalisms for reasoning about action and change have been proposed in the literature, their semantic adequacy has primarily been tested using tiny domains that highlight some particular aspect or problem. However, since some of the classical problems are completely or partially solved and since powerful tools are available, it is now necessary to start modeling more complex domains. This paper presents a methodology for handling such domains in a systematic manner using an object-oriented framework and provides several examples of the elaboration tolerance exhibited by the resulting models. [48] 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. Morgan Kaufmann. 2000 [47] Jaroslaw Kachniarz and Andrzej Szalas. 2000. Algorithms based on Symbolic Transformations of Logical Formulas in the RDL Language. In Proceedings of the 2nd Conference on Applications of Computer Science in Mathematics and Economy, pages 101–115. WSIiE, Olsztyn, Poland. [46] Jaroslaw Kachniarz and Andrzej Szalas. 2000. On Rule-Based Approach to the Construction of Logical Transformers. In Proceedings of the 1st International Workshop on Rule-Based Programming (RULE), pages 57–71. Springer Physica-Verlag. [45] Alexander Kleiner, Bernadette Sharp and Oliver Bittel. 2000. Self Organising Maps for Value Estimation to Solve Reinforcement Learning Tasks. In Proc. of the 2nd International Conference on Enterprise Information Systems (ICEIS 2000), pages 74–83. Reinforcement learning has been applied recently more and more for the optimisation of agent behaviours. This approach became popular due to its adaptive and unsupervised learning process. One of the key ideas of this approach is to estimate the value of agent states. For huge state spaces however, it is difficult to implement this approach. As a result, various models were proposed which make use of function approximators, such as neural networks, to solve this problem. This paper focuses on an implementation of value estimation with a particular class of neural networks, known as self organizing maps. Experiments with an agent moving in a gridworld and the autonomous robot Khepera have been carried out to show the benefit of our approach. The results clearly show that the conventional approach, done by an implementation of a look-up table to represent the value function, can be out performed in terms of memory usage and convergence speed. [44] Alexander Kleiner and Bernadette Sharp. 2000. A New Algorithm for Learning Bayesian Classifiers from Data. In Artificial Intelligence and Soft Computing, pages 191–197. We introduce a new algorithm for the induction of classifiers from data, based on Bayesian networks. Basically this problem has already been examined from two perspectives: first, the induction of classifiers by learning algorithms for Bayesian networks, second, the induction of classifiers based on the naive Bayesian classifier. Our approach is located between these two perspectives; it eliminates the disadvantages of both while exploiting their advantages. In contrast to recently appeared refinements of the naive Bayes classifier, which captures single correlations in the data, we have developed an approach which captures multiple correlations and furthermore does a trade-off between complexity and accuracy. In this paper we evaluate the implementation of our approach with data sets from the machine learning repository and data sets artificially generated by Bayesian networks. [43] Marcus Bjäreland and George Fodor. 2000. Execution monitoring of industrial process controllers: an application of Ontological Control. In Prooceedings of the 4th Symposium on Fault Detection, Supervision and Safety for Technical Systems (SAFEPROCESS '00). [42] Mutsumi Nakamura, Chitta Baral and Marcus Bjäreland. 2000. Maintainability: a weaker stabilizability-like notion for high level control of agents. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI), pages 62–66. AAAI Press. ISBN: 978-0-262-51112-4, 978-1-57735-272-3. The goal of most agents is not just to reach a goal state, but rather also (or alternatively) to put restrictions on its trajectory, in terms of states it must avoid and goals that it must ‘maintain’. This is analogous to the notions of ‘safety’ and ‘stability’ in the discrete event systems and temporal logic community. In this paper we argue that the notion of ‘stability’ is too strong for formulating ‘maintenance’ goals of an agent – in particular, reactive and software agents, and give examples of such agents. We present a weaker notion of ‘maintainability’ and show that our agents which do not satisfy the stability criteria, do satisfy the weaker criteria. We give algorithms to test maintainability, and also to generate control for maintainability. We then develop the notion of ‘supportability’ that generalizes both ‘maintainability’ and ‘stabilizability, develop an automata theory that distinguishes between exogenous and control actions, and develop a temporal logic based on it. [41] Fredrik Heintz, Johan Kummeneje and Paul Scerri. 2000. Simulated RoboCup in University Undergraduate Education. In Proceedings of the Fourth Internation Workshop on RoboCup. [40] Patrik Haslum and Peter Jonsson. 2000. Planning with Reduced Operator Sets. In Steve Chien, Subbarao Kambhampati, Craig A. Knoblock, editors, Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS), pages 150–158. AAAI Press. ISBN: 978-1-57735-111-5. Classical propositional STRIPS planning is nothing but the search for a path in the state transition graph induced by the operators in the planning problem. What makes the problem hard is the size and the sometimes adverse structure of this graph. We conjecture that the search for a plan would be more efficient if there were only a small number of paths from the initial state to the goal state. To verify this conjecture, we define the notion of reduced operator sets and describe ways of finding such reduced sets. We demonstrate that some state-of-the-art planners run faster using reduced operator sets. [39] Patrik Haslum and Héctor Geffner. 2000. Admissible Heuristics for Optimal Planning. In Steve Chien, Subbarao Kambhampati, Craig A. Knoblock, editors, Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS), pages 140–149. AAAI Press. ISBN: 978-1-57735-111-5. Note: There is an error in the paper: the condition for commutativity of actions (section "Commutativity Pruning") must also include that neither action adds a precondition of the other. Thus, commutativity is not the same as Graphplan-style "non-interference". hsp and hspr are two recent planners that search the state-space using an heuristic function extracted from Strips encodings. hsp does a forward search from the initial state recomputing the heuristic in every state, while hspr does a regression search from the goal computing a suitable representation of the heuristic only once. Both planners have shown good performance, often producing solutions that are competitive in time and number of actions with the solutions found by Graphplan and sat planners. hsp and hsp r, however, are not optimal planners. This is because the heuristic function is not admissible and the search algorithms are not optimal. In this paper we address this problem. We formulate a new admissible heuristic for planning, use it to guide an ida search, and empirically evaluate the resulting optimal planner over a number of domains. The main contribution is the idea underlying the heuristic that yields not one but a whole family of polynomial and admissible heuristics that trade accuracy for efficiency. The formulation is general and sheds some light on the heuristics used in hsp and Graphplan, and their relation. It exploits the factored (Strips) representation of planning problems, mapping shortest-path problems in state-space into suitably defined shortest-path problems in atom-space. The formulation applies with little variation to sequential and parallel planning, and problems with different action costs. [38] Fredrik Heintz. 2000. FCFoo99. In Proceedings of RoboCup-99: Robot Soccer World Cup III (RoboCup), pages 563–566. In series: Lecture Notes in Computer Science #1856. Springer London. ISBN: 3-540-41043-0. [37] 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). In series: Frontiers in Artificial Intelligence and Applications #54. IOS Press. ISBN: 1586030132. 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. [36] 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. ISBN: 3-540-41044-9. 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. [35] 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. 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. [34] 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 [33] Andreas Nonnengart, Hans-Jürgen Ohlbach and Andrzej Szalas. 1999. Elimination of Predicate Quantifiers. In Logic, Language and Reasoning. Essays in Honor of Dov Gabbay, Part I, pages 159–181. Kluwer Academic Publishers. [32] Patrik Haslum. 1999. Model Checking by Random Walk. In Proceedings of the ECSEL Workshop (CCSSE). While model checking algorithms are in theory efficient, they are in practice hampered by the explosive growth of system models. We show that for certain specifications the model cheking problem reduces to a question of reachability in the system state transition graph, and apply a simple, randomized algorithm to this problem. [31] Marcus Bjäreland and Peter Jonsson. 1999. Exploiting bipartiteness to identify yet another tractable subclass of CSP. In Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP), pages 118–128. In series: Lecture Notes in Computer Science #1713. Springer. DOI: 10.1007/978-3-540-48085-3_9. The class of constraint satisfaction problems (CSPs) over finite domains has been shown to be NP-complete, but many tractable subclasses have been identified in the literature. In this paper we are interested in restrictions on the types of constraint relations in CSP instances. By a result of Jeavons et al. we know that a key to the complexity of classes arising from such restrictions is the closure properties of the sets of relations. It has been shown that sets of relations that are closed under constant, majority, affine, or associative, commutative, and idempotent (ACI) functions yield tractable subclasses of CSP. However, it has been unknown whether other closure properties may generate tractable subclasses. In this paper we introduce a class of tractable (in fact, SL-complete) CSPs based on bipartite graphs. We show that there are members of this class that are not closed under constant, majority, affine, or ACI functions, and that it, therefore, is incomparable with previously identified classes. [30] Patrik Haslum and Peter Jonsson. 1999. Some results on the complexity of planning with incomplete information. In Proceedings of the 5th European Conference on Planning (ECP), pages 308–318. In series: Lecture Notes in Computer Science #1809. Springer. DOI: 10.1007/10720246_24. Planning with incomplete information may mean a number of different things, that certain facts of the initial state are not known, that operators can have random or nondeterministic effects, or that the plans created contain sensing operations and are branching. Study of the complexity of incomplete information planning has so far been concentrated on probabilistic domains, where a number of results have been found. We examine the complexity of planning in nondeterministic propositional domains. This differs from domains involving randomness, which has been well studied, in that for a nondeterministic choice, not even a probability distribution over the possible outcomes is known. The main result of this paper is that the non-branching plan existence problem in unobservable domains with an expressive operator formalism is EXPSPACE-complete. We also discuss several restrictions, which bring the complexity of the problem down to PSPACF-complete, and extensions to the fully and partially observable cases. [29] 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. [28] 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. [27] 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. [26] Silvia Coradeschi, Lars Karlsson and Klas Nordberg. 1999. Integration of vision and decision-making in an autonomous airborne vehicle for traffic surveillance. In Proceedings of the International Conference on Vision Systems '99: Grand Canary. In this paper we present a system which integrates computer vision and decision-making in an autonomous airborne vehicle that performs traffic surveillance tasks. The main factors that make the integration of vision and decision-making a challenging problem are: the qualitatively different kind of information at the decision-making and vision levels, the need for integration of dynamically acquired information with a priori knowledge, e.g. GIS information, and the need of close feedback and guidance of the vision module by the decision-making module. Given the complex interaction between the vision module and the decision-making module we propose the adoption of an intermediate structure, called Scene Information Manager, and describe its structure and functionalities. 1998 [25] 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. [24] 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. [23] 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 [22] Thomas Drakengren and Marcus Bjäreland. 1997. Reasoning about Action in Polynomial Time. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI). [21] Marcus Bjäreland and Lars Karlsson. 1997. Reasoning by Regression: Pre- and Postdiction Procedures for Logics of Action and Change with Nondeterminism. In Proceedings of the 15th International Joint Conference on Artficial Intelligence (IJCAI). [20] Silvia Coradeschi, Klas Nordberg and Lars Karlsson. 1997. Integration of vision and reasoning in an airborne autonomous vehicle for traffic surveillance. In Knowledge Based Computer Vision, Seminar-Report 196: Schloss Dagstuhl, Germany. 1996 [19] 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. [18] 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. [17] 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 [16] 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 [15] 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 [14] Andrzej Szalas. 1994. Genetic Algorithms for Decision Problems. In Proceedings of the 6th International Conference on Artificial Intelligence and Information-Control Systems of Robots (AIICSR), pages 383–390. World Scientific. ISBN: 981-02-1877-X. [13] 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. [12] Patrick Doherty. 1994. Reasoning about action and change using occlusion. In 11th European Conference on Artificial Intelligence,1994. John Wiley and Sons. 1992 [11] 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. [10] 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. [9] 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. [8] Patrick Doherty, Dimiter Driankov and A. Tsoukias. 1992. Partial logics and partial preferences. In International Conference on Economics/Management and Information Technology,1992. 1991 [7] Patrick Doherty and Dimiter Driankov. 1991. A non-monotonic fuzzy logic. In International Fuzzy Systems Association, Fourth World Congress,1991. [6] 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 [5] 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 [4] 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 [3] 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. [2] 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. 1987 [1] R. J. Cunningham, Andreas Nonnengart and Andrzej Szalas. 1987. A Compositional Method for the Design and Proof of Asynchronous Processes. In Proceedings of the 4th Annual ESPRIT Conference (ESPRIT), pages 566–580. North-Holland. ISBN: 0-444-70333-0.