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

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.

关键词：

Parameterized algorithms for Coordinated Motion Planning: Minimizing Energy 51

学校读者我要写书评

暂无评论

Parameterized Algorithms for Coordinated Motion Planning: Mi...

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Deligkas, Argyrios Eiben, Eduard Ganian, Robert Kanj, Iyad Ramanujan, M.S. Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria School of Computing DePaul University ChicagoIL United States Department of Computer Science University of Warwick Coventry United Kingdom

ISBN: (纸本)9783959773225

We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of k robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously-established results that were restricted to solid grids. We design a fixed-parameter additive approximation algorithm for this problem parameterized by k alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied coordinated motion planning problems: (1) A fixed-parameter algorithm, parameterized by k, for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle;and (2) a fixed-parameter algorithm, parameterized by k plus the treewidth of the input graph, for the standard Coordinated Motion Planning (CMP) problem in which we need to route all the k robots to their destinations. The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by k on graphs of bounded outerplanarity, which include bounded-height subgrids. We complement the above results with a lower bound which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts the recently-obtained tractability of the problem on solid grids under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth – a class including, among others, all graphs of bounded genus. © Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan.

关键词： Parameterization

Algorithm and hardness results on liar’s dominating set and k-tuple dominating set

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Banerjee, Sandip Bhore, Sujoy Department of Computer Science Hebrew University of Jerusalem Israel Algorithms and Complexity Group Technische Universität Wien Austria

Given a graph G = (V, E), the dominating set problem asks for a minimum subset of vertices D ⊆ V such that every vertex u ∈ V \D is adjacent to at least one vertex v ∈ D. That is, the set D satisfies the condition that |N[v] ∩ D| ≥ 1 for each v ∈ V , where N[v] is the closed neighborhood of v. In this paper, we study two variants of the classical dominating set problem: k-tuple dominating set (k-DS) problem and Liar’s dominating set (LDS) problem, and obtain several algorithmic and hardness results. On the algorithmic side, we present a constant factor (112 )-approximation algorithm for the Liar’s dominating set problem on unit disk graphs. Then, we obtain a PTAS for the k-tuple dominating set problem on unit disk graphs. On the hardness side, we show a Ω(n2) bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar’s dominating set problem as well as for the k-tuple dominating set problem. Furthermore, we prove that the Liar’s dominating set problem on bipartite graphs is W[2]-hard. Copyright © 2019, The Authors. All rights reserved.

关键词： Graph theory

Detours in Directed Graphs 39

学校读者我要写书评

暂无评论

Detours in Directed Graphs

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

作者： Fomin, Fedor V. Golovach, Petr A. Lochet, William Sagunov, Danil Simonov, Kirill Saurabh, Saket Department of Informatics University of Bergen Norway St. Petersburg Department of V.A. Steklov Institute of Mathematics Russia JetBrains Research Saint Petersburg Russia Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences HBNI Chennai India

ISBN: (纸本)9783959772228

We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s, t)-path of length at least distG(s, t) + k (where distG(s, t) denotes the length of a shortest path from s to t). Bezáková et al. [7] proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2O(k) · n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2O(k) · nO(1) time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G) + k (diam(G) denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path above Diameter is NP-complete even for k = 1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path above Diameter is solvable in polynomial time for each k ∈ {1, . . ., 4} and is NP-complete for every k ≥ 5. The parameterized complexity of Longest Detour on general directed graphs remains an interesting open problem. © Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh.

关键词： Directed graphs

Crossing-optimal extension of simple drawings

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Ganian, Robert Hamm, Thekla Klute, Fabian Parada, Irene Vogtenhuber, Birgit Algorithms and Complexity Group TU Wien Austria Utrecht University Netherlands TU Eindhoven Netherlands Graz University of Technology Austria

In extension problems of partial graph drawings one is given an incomplete drawing of an input graph G and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, only recently it has been shown that the extension problem of simple drawings is NP-hard even when the task is to insert a single edge. In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for k-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing. © 2020, CC BY.

关键词： Graph theory

Path-contractions, edge deletions and connectivity preservation

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Gutin, Gregory Ramanujan, M.S. Reidl, Felix Wahlstrom, Magnus Royal Holloway University University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Vienna Austria

We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, Vertex-deletion Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while deleting exactly k vertices, and Path-contraction Preserving Strong Connectivity, in which the operation of path contraction on arcs is used instead. The parameterized tractability of this last problem was posed by Bang-Jensen and Yeo [DAM 2008] as an open question and we answer it here in the negative: Both variants of preserving strong connectivity are W[1]-hard. Preserving biconnectivity, on the other hand, turns out to be fixed parameter tractable and we provide a 2O(k log k)nO(1)-algorithm that solves Weighted Biconnectivity Deletion. Further, we show that the unweighted case even admits a randomized polynomial kernel. All our results provide further interesting data points for the systematic study of connectivity-preservation constraints in the parameterized setting. Copyright © 2017, The Authors. All rights reserved.

关键词： Parameterization

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chew, Leroy de Colnet, Alexis Slivovsky, Friedrich Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer Science University of Liverpool Liverpool United Kingdom

Parity reasoning is challenging for Conflict-Driven Clause Learning (CDCL) SAT solvers. This has been observed even for simple formulas encoding two contradictory parity constraints with different variable orders (Chew and Heule 2020). We provide an analytical explanation for their hardness by showing that they require exponential resolution refutations with high probability when the variable order is chosen at random. We obtain this result by proving that these formulas, which are known to be Tseitin formulas, have Tseitin graphs of linear treewidth with high probability. Since such Tseitin formulas require exponential resolution proofs, our result follows. We generalize this argument to a new class of formulas that capture a basic form of parity reasoning involving a sum of two random parity constraints with random orders. Even when the variable order for the sum is chosen favorably, these formulas remain hard for resolution. In contrast, we prove that they have short DRAT refutations. We show experimentally that the running time of CDCL SAT solvers on both classes of formulas grows exponentially with their treewidth. © 2024, CC BY.

关键词： Hardness

Theoretical analysis of diversity mechanisms for global exploration 08

学校读者我要写书评

暂无评论

Theoretical analysis of diversity mechanisms for global expl...

10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008

作者： Friedrich, Tobias Oliveto, Pietro S. Sudholt, Dirk Witt, Carsten Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarbrücken Germany School of Computer Science University of Birmingham Birmingham United Kingdom Fakultät für Informatik LS 2 Technische Universität Dortmund Dortmund Germany

ISBN: (纸本)9781605581309

Maintaining diversity is important for the performance of evolutionary algorithms. Diversity mechanisms can enhance global exploration of the search space and enable crossover to find dissimilar individuals for recombination. We focus on the global exploration capabilities of mutation-based algorithms. Using a simple bimodal test function and rigorous runtime analyses, we compare well-known diversity mechanisms like deterministic crowding, fitness sharing, and others with a plain algorithm without diversification. We show that diversification is necessary for global exploration, but not all mechanisms succeed in finding both optima efficiently. Copyright 2008 ACM.

关键词： Evolutionary algorithms

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.

关键词：