检索结果-内蒙古大学图书馆

Learning Depth Vision-Based Personalized Robot Navigation From Dynamic Demonstrations in Virtual Reality

学校读者我要写书评

暂无评论

Learning Depth Vision-Based Personalized Robot Navigation Fr...

IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

作者： Jorge de Heuvel Nathan Corral Benedikt Kreis Jacobus Conradi Anne Driemel Maren Bennewitz Humanoid Robots Lab Group for Algorithms and Complexity University of Bonn Lamarr Institute for Machine Learning and Artificial Intelligence Germany

For the best human-robot interaction experience, the robot's navigation policy should take into account personal preferences of the user. In this paper, we present a learning framework complemented by a perception pipeline to train a depth vision-based, personalized navigation controller from user demonstrations. Our virtual reality interface enables the demonstration of robot navigation trajectories under motion of the user for dynamic interaction scenarios. The novel perception pipeline enrolls a variational autoencoder in combination with a motion predictor. It compresses the perceived depth images to a latent state representation to enable efficient reasoning of the learning agent about the robot's dynamic environment. In a detailed analysis and ablation study, we evaluate different configurations of the perception pipeline. To further quantify the navigation controller's quality of personalization, we develop and apply a novel metric to measure preference reflection based on the Frechet Distance. We discuss the robot's navigation performance in various virtual scenes and demonstrate the first personalized robot navigation controller that solely relies on depth images. A supplemental video highlighting our approach is available online 1 1 Full video: ***/publications/deheuve123iros_***4.

关键词：

Further Exploiting c-Closure for FPT algorithms and Kernels for Domination Problems 39

学校读者我要写书评

暂无评论

Further Exploiting c-Closure for FPT Algorithms and Kernels ...

39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022

作者： Kanesh, Lawqueen Madathil, Jayakrishnan Roy, Sanjukta Sahu, Abhishek Saurabh, Saket National University of Singapore Singapore Chennai Mathematical Institute India Algorithms and Complexity Group TU Wien Austria The Institute of Mathematical Sciences HBNI Chennai India University of Bergen Norway

ISBN: (纸本)9783959772228

For a positive integer c, a graph G is said to be c-closed if every pair of non-adjacent vertices in G have at most c - 1 neighbours in common. The closure of a graph G, denoted by cl(G), is the least positive integer c for which G is c-closed. The class of c-closed graphs was introduced by Fox et al. [ICALP ‘18 and SICOMP ‘20]. Koana et al. [ESA ‘20] started the study of using cl(G) as an additional structural parameter to design kernels for problems that are W-hard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set and (Threshold) Dominating Set, and showed that each of these problems admits a polynomial kernel, either w.r.t. the parameter k + c or w.r.t. the parameter k for each fixed value of c. Here, k is the solution size and c = cl(G). The work of Koana et al. left several questions open, one of which was whether the Perfect Code problem admits a fixed-parameter tractable (FPT) algorithm and a polynomial kernel on c-closed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixed-parameter tractable w.r.t. the parameter k + cl(G), whereas Partial Dominating Set, parameterized by k is W[1]-hard even when cl(G) = 2. We also show that for each fixed c, Perfect Code admits a polynomial kernel on the class of c-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs, unless NP ⊆ co-NP/poly. © Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh.

关键词： Graphic methods

A Simple Partially Embedded Planarity Test Based on Vertex-Addition

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Fink, Simon D. Rutter, Ignaz Sandhya, T.P. Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Informatics and Mathematics University of Passau Germany Stockholm University Department of Mathematics Sweden

In the Partially Embedded Planarity problem, we are given a graph G together with a topological drawing of a subgraph H of G. The task is to decide whether the drawing can be extended to a drawing of the whole graph such that no two edges cross. Angelini et al. gave a linear-time algorithm for solving this problem in 2010 [1,2]. While their paper constitutes a significant result, the algorithm described therein is highly complex: it uses several layers of decompositions according to connectivity of both G and H, its description spans more than 30 pages, and can hardly be considered implementable. We give an independent linear-time algorithm that works along the well-known vertex-addition planarity test by Booth and Lueker [5,6]. We modify the PC-tree as underlying data structure used for representing all planar drawing possibilities in a natural way to also respect the restrictions given by the prescribed drawing of the subgraph H. The testing algorithm and its proof of correctness only require small adaptations from the comparatively much simpler generic planarity test, of which several implementations exist. If the test succeeds, an embedding can be constructed using the same approaches that are used for the generic planarity test. © 2024, CC BY-SA.

关键词： Trees (mathematics)

MosaicSets: Embedding Set Systems into Grid Graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Rottmann, Peter Wallinger, Markus Bonerath, Annika Gedicke, Sven Nöllenburg, Martin Haunert, Jan-Henrik The Geoinformation Group of the University of Bonn Germany The Algorithms and Complexity Group of the Technical University of Vienna Austria

Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets: a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews. © 2022, CC BY.

关键词： Visualization

Explaining Decisions in ML Models: a Parameterized complexity Analysis

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ordyniak, Sebastian Paesani, Giacomo Rychlicki, Mateusz Szeider, Stefan School of Computing University of Leeds United Kingdom Dipartimento di Informatica Sapienza University of Rome Italy Algorithms and Complexity Group TU Wien Vienna Austria

This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the prevalent black-box perception, our study focuses on models with transparent internal mechanisms. We address two principal types of explanation problems: abductive and contrastive, both in their local and global variants. Our analysis encompasses diverse ML models, including Decision Trees, Decision Sets, Decision Lists, Ordered Binary Decision Diagrams, Random Forests, and Boolean Circuits, and ensembles thereof, each offering unique explanatory challenges. This research fills a significant gap in explainable AI (XAI) by providing a foundational understanding of the complexities of generating explanations for these models. This work provides insights vital for further research in the domain of XAI, contributing to the broader discourse on the necessity of transparency and accountability in AI systems. Copyright © 2024, The Authors. All rights reserved.

关键词： Decision trees

Pseudorandom Finite Models

学校读者我要写书评

暂无评论

Pseudorandom Finite Models

Annual Symposium on Logic in Computer Science

作者： Jan Dreier Jamie Tucker-Foltz Algorithms and Complexity Group TU Wien Vienna Austria School of Engineering and Applied Sciences Harvard University Allston MA USA

We study pseudorandomness and pseudorandom generators from the perspective of logical definability. Building on results from ordinary derandomization and finite model theory, we show that it is possible to deterministically construct, in polynomial time, graphs and relational structures that are statistically indistinguishable from random structures by any sentence of first order or least fixed point logics. This raises the question of whether such constructions can be implemented via logical transductions from simpler structures with less entropy. In other words, can logical formulas be pseudorandom generators? We provide a complete classification of when this is possible for first order logic, fixed point logic, and fixed point logic with parity, and provide partial results and conjectures for first order logic with parity.

关键词：

Level Planarity Is More Difficult Than We Thought

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Fink, Simon D. Pfretzschner, Matthias Rutter, Ignaz Stumpf, Peter Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Computer Science and Mathematics University of Passau Germany Charles University Prague Czech Republic

We consider three simple quadratic time algorithms for the problem Level Planarity and give a level-planar instance that they either falsely report as negative or for which they output a drawing that is not level plan... 详细信息

关键词： Consensus algorithm

Worbel: Aggregating Point Labels into Word Clouds

学校读者我要写书评

暂无评论

Worbel: Aggregating Point Labels into Word Clouds

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Technology Bombay Main Gate Rd IIT Area Powai Maharashtra Mumbai400076 India Algorithms and Complexity Group Technische Universität Wien Institute of Logic and Computation Favoritenstraße 9-11 E192-01 Wien1040 Austria

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this article, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consist of a set of points grouped into categories and our aim is to place multiple disjoint and axis-Aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing a heuristic with (optional) exact components using SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several synthetic and real-world data sets. Our experiments show that the fully heuristic approach produces solutions of comparable quality to heuristics combined with exact SAT models, while running much faster. © 2023 Copyright held by the owner/author(s).

关键词： Visualization

Worbel: Aggregating Point Labels into Word Clouds 21

学校读者我要写书评

暂无评论

Worbel: Aggregating Point Labels into Word Clouds

29th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2021

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Science Education and Research Bhopal Bhopal India Algorithms and Complexity Group Tu Wien Vienna Austria

ISBN: (纸本)9781450386647

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster. © 2021 ACM.

关键词： Visualization