English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of motion planning for a collection of $n$ labeled unitdisc robots in a polygonal environment. We assume that the robots haverevolving areas around their start and final positions: that each start andeach final is contained in a radius $2$ disc lying in the free space, notnecessarily concentric with the start or final position, which is free fromother start or final positions. This assumption allows a weakly-monotone motionplan, in which robots move according to an ordering as follows: during the turnof a robot $R$ in the ordering, it moves fully from its start to finalposition, while other robots do not leave their revolving areas. As $R$ passesthrough a revolving area, a robot $R'$ that is inside this area may move withinthe revolving area to avoid a collision. Notwithstanding the existence of amotion plan, we show that minimizing the total traveled distance in thissetting, specifically even when the motion plan is restricted to beweakly-monotone, is APX-hard, ruling out any polynomial-time$(1+\epsilon)$-approximation algorithm.  On the positive side, we present the first constant-factor approximationalgorithm for computing a feasible weakly-monotone motion plan. The totaldistance traveled by the robots is within an $O(1)$ factor of that of theoptimal motion plan, which need not be weakly monotone. Our algorithm extendsto an online setting in which the polygonal environment is fixed but theinitial and final positions of robots are specified in an online manner.Finally, we observe that the overhead in the overall cost that we add whileediting the paths to avoid robot-robot collision can vary significantlydepending on the ordering we chose. Finding the best ordering in this respectis known to be NP-hard, and we provide a polynomial time $O(\log n \log \logn)$-approximation algorithm for this problem.

Multi-Robot Motion Planning for Unit Discs with Revolving Areas