Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEscaping an Infinitude of Lions
140
0
0.0
(
0
)
Added by
Mikkel Abrahamsen
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the following game played in the Euclidean plane: There is any countable set of unit speed lions and one fast man who can run with speed $1+varepsilon$ for some value $varepsilon>0$. Can the man survive? We answer the question in the affirmative for any $varepsilon>0$.
rate research
Read More
Suppose an escaping player moves continuously at maximum speed 1 in the interior of a region, while a pursuing player moves continuously at maximum speed $r$ outside the region. For what $r$ can the first player escape the region, that is, reach the boundary a positive distance away from the pursuing player, assuming optimal play by both players? We formalize a model for this infinitesimally alternating 2-player game that we prove has a unique winner in any region with locally rectifiable boundary, avoiding pathological behaviors (where both players can have winning strategies) previously identified for pursuit-evasion games such as the Lion and Man problem in certain metric spaces. For some regions, including both equilateral triangle and square, we give exact results for the critical speed ratio, above which the pursuing player can win and below which the escaping player can win (and at which the pursuing player can win). For simple polygons, we give a simple formula and polynomial-time algorithm that is guaranteed to give a 10.89898-approximation to the critical speed ratio, and we give a pseudopolynomial-time approximation scheme for arbitrarily approximating the critical speed ratio. On the negative side, we prove NP-hardness of the problem for polyhedral domains in 3D, and prove stronger results (PSPACE-hardness and NP-hardness even to approximate) for generalizations to multiple escaping and pursuing players.
We study a simple reconfigurable robot model which has not been previously examined: cubic robots comprised of three-dimensional cubic modules which can slide across each other and rotate about each others edges. We demonstrate that the cubic robot model is universal, i.e., that an n-module cubic robot can reconfigure itself into any specified n-module configuration. Additionally, we provide an algorithm that efficiently plans and executes cubic robot motion. Our results directly extend to a d-dimensional model.
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are pivots, where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using $O(n^3)$ monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN18] that we consider of independent interest.
The chaotic behaviour of the motion of the planets in our Solar System is well established. In this work to model a hypothetical extrasolar planetary system our Solar System was modified in such a way that we replaced the Earth by a more massive planet and let the other planets and all the orbital elements unchanged. The major result of former numerical experiments with a modified Solar System was the appearance of a chaotic window at $kappa_E in (4,6)$, where the dynamical state of the system was highly chaotic and even the body with the smallest mass escaped in some cases. On the contrary for very large values of the mass of the Earth, even greater than that of Jupiter regular dynamical behaviour was observed. In this paper the investigations are extended to the complete Solar System and showed, that this chaotic window does still exist. Tests in different Solar Systems clarified that including only Jupiter and Saturn with their actual masses together with a more massive Earth ($4 < kappa_E < 6$) perturbs the orbit of Mars so that it can even be ejected from the system. Using the results of the Laplace-Lagrange secular theory we found secular resonances acting between the motions of the nodes of Mars, Jupiter and Saturn. These secular resonances give rise to strong chaos, which is the cause of the appearance of the instability window.
We present a number of breakthroughs for coordinated motion planning, in which the objective is to reconfigure a swarm of labeled convex objects by a combination of parallel, continuous, collision-free translations into a given target arrangement. Problems of this type can be traced back to the classic work of Schwartz and Sharir (1983), who gave a method for deciding the existence of a coordinated motion for a set of disks between obstacles; their approach is polynomial in the complexity of the obstacles, but exponential in the number of disks. Other previous work has largely focused on {em sequential} schedules, in which one robot moves at a time. We provide constant-factor approximation algorithms for minimizing the execution time of a coordinated, {em parallel} motion plan for a swarm of robots in the absence of obstacles, provided some amount of separability. Our algorithm achieves {em constant stretch factor}: If all robots are at most $d$ units from their respective starting positions, the total duration of the overall schedule is $O(d)$. Extensions include unlabeled robots and different classes of robots. We also prove that finding a plan with minimal execution time is NP-hard, even for a grid arrangement without any stationary obstacles. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor $Omega(N^{1/4})$ may be required. On the positive side, we establish a stretch factor of $O(N^{1/2})$ even in this case.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
