-
Online Bin Covering with Exact Parameter Advice
Authors:
Andrej Brodnik,
Bengt J. Nilsson,
Gordana Vujovic
Abstract:
We show an asymptotic 2/3-competitive strategy for the bin covering problem using O(b+log n) bits of advice, where b is the number of bits used to encode a rational value and n is the length of the input sequence.
We show an asymptotic 2/3-competitive strategy for the bin covering problem using O(b+log n) bits of advice, where b is the number of bits used to encode a rational value and n is the length of the input sequence.
△ Less
Submitted 24 September, 2023;
originally announced September 2023.
-
Approximation Algorithms for the Two-Watchman Route in a Simple Polygon
Authors:
Bengt J. Nilsson,
Eli Packer
Abstract:
The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their le…
▽ More
The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times O(n^8) and O(n^4) respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in O(n^2) time, i.e., when two starting points of the two tours are given as input.
△ Less
Submitted 23 September, 2023;
originally announced September 2023.
-
Refining Obstacle Perception Safety Zones via Maneuver-Based Decomposition
Authors:
Sever Topan,
Yuxiao Chen,
Edward Schmerling,
Karen Leung,
Jonas Nilsson,
Michael Cox,
Marco Pavone
Abstract:
A critical task for developing safe autonomous driving stacks is to determine whether an obstacle is safety-critical, i.e., poses an imminent threat to the autonomous vehicle. Our previous work showed that Hamilton Jacobi reachability theory can be applied to compute interaction-dynamics-aware perception safety zones that better inform an ego vehicle's perception module which obstacles are conside…
▽ More
A critical task for developing safe autonomous driving stacks is to determine whether an obstacle is safety-critical, i.e., poses an imminent threat to the autonomous vehicle. Our previous work showed that Hamilton Jacobi reachability theory can be applied to compute interaction-dynamics-aware perception safety zones that better inform an ego vehicle's perception module which obstacles are considered safety-critical. For completeness, these zones are typically larger than absolutely necessary, forcing the perception module to pay attention to a larger collection of objects for the sake of conservatism. As an improvement, we propose a maneuver-based decomposition of our safety zones that leverages information about the ego maneuver to reduce the zone volume. In particular, we propose a "temporal convolution" operation that produces safety zones for specific ego maneuvers, thus limiting the ego's behavior to reduce the size of the safety zones. We show with numerical experiments that maneuver-based zones are significantly smaller (up to 76% size reduction) than the baseline while maintaining completeness.
△ Less
Submitted 11 August, 2023;
originally announced August 2023.
-
Guarding Polyominoes under $k$-Hop Visibility
Authors:
Omrit Filtser,
Erik Krohn,
Bengt J. Nilsson,
Christian Rieck,
Christiane Schmidt
Abstract:
We study the Art Gallery Problem under $k$-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most $k$.
In this paper, we show that the VC dimension of this problem is $3$ in simple polyominoes, and $4$ in polyominoes with hole…
▽ More
We study the Art Gallery Problem under $k$-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most $k$.
In this paper, we show that the VC dimension of this problem is $3$ in simple polyominoes, and $4$ in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a $2\times 2$ block of cells). Complementarily, we present a linear-time $4$-approximation algorithm for simple $2$-thin polyominoes (which do not contain a $3\times 3$ block of cells) for all $k\in \mathbb{N}$.
△ Less
Submitted 15 January, 2024; v1 submitted 1 August, 2023;
originally announced August 2023.
-
APX-Hardness of the Minimum Vision Points Problem
Authors:
Mayank Chaturvedi,
Bengt J. Nilsson
Abstract:
Placing a minimum number of guards on a given watchman route in a polygonal domain is called the {\em minimum vision points problem}. We prove that finding the minimum number of vision points on a shortest watchman route in a simple polygon is APX-Hard. We then extend the proof to the class of rectilinear polygons having at most three dent orientations.
Placing a minimum number of guards on a given watchman route in a polygonal domain is called the {\em minimum vision points problem}. We prove that finding the minimum number of vision points on a shortest watchman route in a simple polygon is APX-Hard. We then extend the proof to the class of rectilinear polygons having at most three dent orientations.
△ Less
Submitted 10 July, 2022;
originally announced July 2022.
-
Opposing Half Guards
Authors:
Erik Krohn,
Bengt J. Nilsson,
Christiane Schmidt
Abstract:
We study the art gallery problem for opposing half guards: guards that can either see to their left or to their right only. We present art gallery theorems, show that the location of half guards in 2-guardable polygons is not restricted to extensions, show that the problem is NP-hard in monotone polygons, and present approximation algorithms for spiral and staircase polygons.
We study the art gallery problem for opposing half guards: guards that can either see to their left or to their right only. We present art gallery theorems, show that the location of half guards in 2-guardable polygons is not restricted to extensions, show that the problem is NP-hard in monotone polygons, and present approximation algorithms for spiral and staircase polygons.
△ Less
Submitted 10 July, 2022;
originally announced July 2022.
-
Interaction-Dynamics-Aware Perception Zones for Obstacle Detection Safety Evaluation
Authors:
Sever Topan,
Karen Leung,
Yuxiao Chen,
Pritish Tupekar,
Edward Schmerling,
Jonas Nilsson,
Michael Cox,
Marco Pavone
Abstract:
To enable safe autonomous vehicle (AV) operations, it is critical that an AV's obstacle detection module can reliably detect obstacles that pose a safety threat (i.e., are safety-critical). It is therefore desirable that the evaluation metric for the perception system captures the safety-criticality of objects. Unfortunately, existing perception evaluation metrics tend to make strong assumptions a…
▽ More
To enable safe autonomous vehicle (AV) operations, it is critical that an AV's obstacle detection module can reliably detect obstacles that pose a safety threat (i.e., are safety-critical). It is therefore desirable that the evaluation metric for the perception system captures the safety-criticality of objects. Unfortunately, existing perception evaluation metrics tend to make strong assumptions about the objects and ignore the dynamic interactions between agents, and thus do not accurately capture the safety risks in reality. To address these shortcomings, we introduce an interaction-dynamics-aware obstacle detection evaluation metric by accounting for closed-loop dynamic interactions between an ego vehicle and obstacles in the scene. By borrowing existing theory from optimal control theory, namely Hamilton-Jacobi reachability, we present a computationally tractable method for constructing a ``safety zone'': a region in state space that defines where safety-critical obstacles lie for the purpose of defining safety metrics. Our proposed safety zone is mathematically complete, and can be easily computed to reflect a variety of safety requirements. Using an off-the-shelf detection algorithm from the nuScenes detection challenge leaderboard, we demonstrate that our approach is computationally lightweight, and can better capture safety-critical perception errors than a baseline approach.
△ Less
Submitted 24 June, 2022;
originally announced June 2022.
-
Online Two-Dimensional Vector Packing with Advice
Authors:
Bengt J. Nilsson,
Gordana Vujovic
Abstract:
We consider the online two-dimensional vector packing problem, showing a lower bound of $11/5$ on the competitive ratio of any {\sc AnyFit} strategy for the problem. We provide strategies with competitive ratio $\max\!\left\{2,6\big/\big(1+3\tan(π/4-γ/2)\big)+ε\right\}$ and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range…
▽ More
We consider the online two-dimensional vector packing problem, showing a lower bound of $11/5$ on the competitive ratio of any {\sc AnyFit} strategy for the problem. We provide strategies with competitive ratio $\max\!\left\{2,6\big/\big(1+3\tan(π/4-γ/2)\big)+ε\right\}$ and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range $[π/4-γ/2,π/4+γ/2]$, for $0\leqγ<π/3$ and $\max\left\{5/2,4\big/\big(1+2\tan(π/4-γ/2)\big)+ε\right\}$ and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range $[π/4-γ/2,π/4+γ/2]$, for $0\leqγ\leqπ/3$. In addition, we give a $5/2$-competitive strategy also using logarithmic advice for the unrestricted vectors case. These results should be contrasted to the currently best competitive strategy, FirstFit, having competitive ratio~$27/10$.
△ Less
Submitted 21 April, 2022;
originally announced April 2022.
-
Punctuation restoration in Swedish through fine-tuned KB-BERT
Authors:
John Björkman Nilsson
Abstract:
Presented here is a method for automatic punctuation restoration in Swedish using a BERT model. The method is based on KB-BERT, a publicly available, neural network language model pre-trained on a Swedish corpus by National Library of Sweden. This model has then been fine-tuned for this specific task using a corpus of government texts. With a lower-case and unpunctuated Swedish text as input, the…
▽ More
Presented here is a method for automatic punctuation restoration in Swedish using a BERT model. The method is based on KB-BERT, a publicly available, neural network language model pre-trained on a Swedish corpus by National Library of Sweden. This model has then been fine-tuned for this specific task using a corpus of government texts. With a lower-case and unpunctuated Swedish text as input, the model is supposed to return a grammatically correct punctuated copy of the text as output. A successful solution to this problem brings benefits for an array of NLP domains, such as speech-to-text and automated text. Only the punctuation marks period, comma and question marks were considered for the project, due to a lack of data for more rare marks such as semicolon. Additionally, some marks are somewhat interchangeable with the more common, such as exclamation points and periods. Thus, the data set had all exclamation points replaced with periods. The fine-tuned Swedish BERT model, dubbed prestoBERT, achieved an overall F1-score of 78.9. The proposed model scored similarly to international counterparts, with Hungarian and Chinese models obtaining F1-scores of 82.2 and 75.6 respectively. As further comparison, a human evaluation case study was carried out. The human test group achieved an overall F1-score of 81.7, but scored substantially worse than prestoBERT on both period and comma. Inspecting output sentences from the model and humans show satisfactory results, despite the difference in F1-score. The disconnect seems to stem from an unnecessary focus on replicating the exact same punctuation used in the test set, rather than providing any of the number of correct interpretations. If the loss function could be rewritten to reward all grammatically correct outputs, rather than only the one original example, the performance could improve significantly for both prestoBERT and the human group.
△ Less
Submitted 14 February, 2022;
originally announced February 2022.
-
$k$-Transmitter Watchman Routes
Authors:
Bengt J. Nilsson,
Christiane Schmidt
Abstract:
We consider the watchman route problem for a $k$-transmitter watchman: standing at point $p$ in a polygon $P$, the watchman can see $q\in P$ if $\overline{pq}$ intersects $P$'s boundary at most $k$ times -- $q$ is $k$-visible to $p$. Traveling along the $k$-transmitter watchman route, either all points in $P$ or a discrete set of points $S\subset P$ must be $k$-visible to the watchman. We aim for…
▽ More
We consider the watchman route problem for a $k$-transmitter watchman: standing at point $p$ in a polygon $P$, the watchman can see $q\in P$ if $\overline{pq}$ intersects $P$'s boundary at most $k$ times -- $q$ is $k$-visible to $p$. Traveling along the $k$-transmitter watchman route, either all points in $P$ or a discrete set of points $S\subset P$ must be $k$-visible to the watchman. We aim for minimizing the length of the $k$-transmitter watchman route.
We show that even in simple polygons the shortest $k$-transmitter watchman route problem for a discrete set of points $S\subset P$ is NP-complete and cannot be approximated to within a logarithmic factor (unless P=NP), both with and without a given starting point. Moreover, we present a polylogarithmic approximation for the $k$-transmitter watchman route problem for a given starting point and $S\subset P$ with approximation ratio $O(\log^2(|S|\cdot n) \log\log (|S|\cdot n) \log(|S|+1))$ (with $|P|=n$).
△ Less
Submitted 12 May, 2023; v1 submitted 3 February, 2022;
originally announced February 2022.
-
Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility
Authors:
Bengt J. Nilsson,
David Orden,
Leonidas Palios,
Carlos Seara,
Paweł Żyliński
Abstract:
We present an $O(nrG)$ time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction $θ$, while $θ$ varies in $[0,180^{\circ})$, obtaining the directions for the tour to be the shortest one over all tours, where $n$ is the number of vertices, $r$ is the number of reflex vertices, and $G\leq r$ is the maximum n…
▽ More
We present an $O(nrG)$ time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction $θ$, while $θ$ varies in $[0,180^{\circ})$, obtaining the directions for the tour to be the shortest one over all tours, where $n$ is the number of vertices, $r$ is the number of reflex vertices, and $G\leq r$ is the maximum number of gates of the polygon used at any time in the algorithm.
△ Less
Submitted 16 July, 2020;
originally announced July 2020.
-
Understanding SSIM
Authors:
Jim Nilsson,
Tomas Akenine-Möller
Abstract:
The use of the structural similarity index (SSIM) is widespread. For almost two decades, it has played a major role in image quality assessment in many different research disciplines. Clearly, its merits are indisputable in the research community. However, little deep scrutiny of this index has been performed. Contrary to popular belief, there are some interesting properties of SSIM that merit suc…
▽ More
The use of the structural similarity index (SSIM) is widespread. For almost two decades, it has played a major role in image quality assessment in many different research disciplines. Clearly, its merits are indisputable in the research community. However, little deep scrutiny of this index has been performed. Contrary to popular belief, there are some interesting properties of SSIM that merit such scrutiny. In this paper, we analyze the mathematical factors of SSIM and show that it can generate results, in both synthetic and realistic use cases, that are unexpected, sometimes undefined, and nonintuitive. As a consequence, assessing image quality based on SSIM can lead to incorrect conclusions and using SSIM as a loss function for deep learning can guide neural network training in the wrong direction.
△ Less
Submitted 29 June, 2020; v1 submitted 24 June, 2020;
originally announced June 2020.
-
Local Routing in Sparse and Lightweight Geometric Graphs
Authors:
Vikrant Ashvinkumar,
Joachim Gudmundsson,
Christos Levcopoulos,
Bengt J. Nilsson,
André van Renssen
Abstract:
Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no $O(1)$-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online ro…
▽ More
Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no $O(1)$-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online routing algorithm that is $O(1)$-competitive. However, a Delaunay triangulation can have $Ω(n)$ vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree.
We show a simple construction, given a set $V$ of $n$ points in the Euclidean plane, of a planar geometric graph on $V$ that has small weight (within a constant factor of the weight of a minimum spanning tree on $V$), constant degree, and that admits a local routing strategy that is $O(1)$-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an $O(1)$-competitive routing strategy.
△ Less
Submitted 9 January, 2022; v1 submitted 23 September, 2019;
originally announced September 2019.
-
Interoperability and machine-to-machine translation model with mappings to machine learning tasks
Authors:
Jacob Nilsson,
Fredrik Sandin,
Jerker Delsing
Abstract:
Modern large-scale automation systems integrate thousands to hundreds of thousands of physical sensors and actuators. Demands for more flexible reconfiguration of production systems and optimization across different information models, standards and legacy systems challenge current system interoperability concepts. Automatic semantic translation across information models and standards is an increa…
▽ More
Modern large-scale automation systems integrate thousands to hundreds of thousands of physical sensors and actuators. Demands for more flexible reconfiguration of production systems and optimization across different information models, standards and legacy systems challenge current system interoperability concepts. Automatic semantic translation across information models and standards is an increasingly important problem that needs to be addressed to fulfill these demands in a cost-efficient manner under constraints of human capacity and resources in relation to timing requirements and system complexity. Here we define a translator-based operational interoperability model for interacting cyber-physical systems in mathematical terms, which includes system identification and ontology-based translation as special cases. We present alternative mathematical definitions of the translator learning task and mappings to similar machine learning tasks and solutions based on recent developments in machine learning. Possibilities to learn translators between artefacts without a common physical context, for example in simulations of digital twins and across layers of the automation pyramid are briefly discussed.
△ Less
Submitted 26 March, 2019;
originally announced March 2019.
-
CLIMEX: A Wireless Physical Layer Security Protocol Based on Clocked Impulse Exchanges
Authors:
Satyam Dwivedi,
John Olof Nilsson,
Panos Papadimitratos,
Peter Händel
Abstract:
A novel method and protocol establishing common secrecy based on physical parameters between two users is proposed. The four physical parameters of users are their clock frequencies, their relative clock phases and the distance between them. The protocol proposed between two users is backed by theoretical model for the measurements. Further, estimators are proposed to estimate secret physical para…
▽ More
A novel method and protocol establishing common secrecy based on physical parameters between two users is proposed. The four physical parameters of users are their clock frequencies, their relative clock phases and the distance between them. The protocol proposed between two users is backed by theoretical model for the measurements. Further, estimators are proposed to estimate secret physical parameters. Physically exchanged parameters are shown to be secure by virtue of their non-observability to adversaries. Under a simplified analysis based on a testbed settings, it is shown that 38 bits of common secrecy can be derived for one run of the proposed protocol among users. The method proposed is also robust against various kinds of active timing attacks and active impersonating adversaries.
△ Less
Submitted 16 August, 2017;
originally announced August 2017.
-
Recursive Bayesian Initialization of Localization Based on Ranging and Dead Reckoning
Authors:
John-Olof Nilsson,
Peter Händel
Abstract:
The initialization of the state estimation in a localization scenario based on ranging and dead reckoning is studied. Specifically, we start with a cooperative localization setup and consider the problem of recursively arriving at a uni-modal state estimate with sufficiently low covariance such that covariance based filters can be used to estimate an agent's state subsequently. A number of simplif…
▽ More
The initialization of the state estimation in a localization scenario based on ranging and dead reckoning is studied. Specifically, we start with a cooperative localization setup and consider the problem of recursively arriving at a uni-modal state estimate with sufficiently low covariance such that covariance based filters can be used to estimate an agent's state subsequently. A number of simplifications/assumptions are made such that the estimation problem can be seen as that of estimating the initial agent state given a deterministic surrounding and dead reckoning. This problem is solved by means of a particle filter and it is described how continual states and covariance estimates are derived from the solution. Finally, simulations are used to illustrate the characteristics of the method and experimental data are briefly presented.
△ Less
Submitted 3 July, 2013;
originally announced July 2013.
-
Cooperative localization by dual foot-mounted inertial sensors and inter-agent ranging
Authors:
John-Olof Nilsson,
Dave Zachariah,
Isaac Skog,
Peter Händel
Abstract:
The implementation challenges of cooperative localization by dual foot-mounted inertial sensors and inter-agent ranging are discussed and work on the subject is reviewed. System architecture and sensor fusion are identified as key challenges. A partially decentralized system architecture based on step-wise inertial navigation and step-wise dead reckoning is presented. This architecture is argued t…
▽ More
The implementation challenges of cooperative localization by dual foot-mounted inertial sensors and inter-agent ranging are discussed and work on the subject is reviewed. System architecture and sensor fusion are identified as key challenges. A partially decentralized system architecture based on step-wise inertial navigation and step-wise dead reckoning is presented. This architecture is argued to reduce the computational cost and required communication bandwidth by around two orders of magnitude while only giving negligible information loss in comparison with a naive centralized implementation. This makes a joint global state estimation feasible for up to a platoon-sized group of agents. Furthermore, robust and low-cost sensor fusion for the considered setup, based on state space transformation and marginalization, is presented. The transformation and marginalization are used to give the necessary flexibility for presented sampling based updates for the inter-agent ranging and ranging free fusion of the two feet of an individual agent. Finally, characteristics of the suggested implementation are demonstrated with simulations and a real-time system implementation.
△ Less
Submitted 21 November, 2013; v1 submitted 12 April, 2013;
originally announced April 2013.
