[music]
Simultaneously steering a large number of agents to goal positions is a common challenge,
whether you are:
an ant army trying to defend your home,
just trying to get home after work,
a densely-packed warehouse of robots delivering products to be packed and shipped,
or a marching band demonstrating your skills.
There are many approaches, ranging from fully distributed solutions
to fully centralized methods such as warehouse robotics, air-traffic control,
and packet routing
In this work we present a number of breakthroughs for coordinated motion planning.
Our goal 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,
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.
Previous work has largely focused on pipelined sequential schedules, in which only robots
on the perimeter move with objectives such as
minimizing the number of moves.
This differs from our objective, which is to minimize the overall time by exploiting
parallel motion of many robots.
A natural lower bound for the necessary time is given by
the maximum distance from a start
to a target location.
The ratio between the achieved overall time
and this maximum distance is called the STRETCH of a schedule.
When is it possible to limit the stretch and achieve good schedules?
That is the focus of this work.
First of all, finding a reconfiguration plan with minimal execution
is NP-hard, even for a grid arrangement without any stationary obstacles.
Here are various parts of the construction.
See our full paper for details.
Before we start with our algorithm, let us take a closer look at possible
ways of rearranging robots.
Because robot collisions are not allowed, direct swaps of adjacent robots are impossible.
However, we can rearrange whole cycles of robots by moving them simultaneously.
Combining several cyclic one-step moves within a six-pack substructure, we can achieve a
swap of neighboring robots.
These swaps can be performed in parallel for disjoint six-packs.
There is a total of twelve different classes of six-packs, so
a set of disjoint swap operations can be realized by a constant
number of parallel rotation steps.
Now let's consider
a starting configuration that we want to rearrange into
this target arrangement.
Making use of the parallel local swaps, we can apply
the parallel rotatesort algorithm of Marberg and Gafni from 1988.
Rotate sort achieves a runtime that is linear in the size of the perimeter of
the bounding box.
However, this does not achieve constant stretch if the maximum distance
is small compared to the perimeter.
So we need more refined algorithmic ideas.
An idea is to subdivide the grid arrangement
into d-sized "tiles".
Then we proceed in two phases: In Phase I
we move each robot to the tile containing its target position.
That is the tricky part.
In Phase II,
we use rotatesort in parallel on all tiles to reach those final
positions in O(d).
Moving the robots to their respective tiles in Phase I proceeds
in four steps.
First, we compute a flow that represents the number of robots moving between tiles.
Note that the flow graph has a limited degree of eight due to the maximum
travel distance of d.
Second, these flows are preprocessed to remove intersecting and bidirectional edges.
In a third step, the cleaned up flow is decomposed into a number of simpler pieces
which are then realized by parallel sets of cyclic moves in the
fourth and final step of Phase I.
As the first step, we take stock
of robots switching tiles.
As no robots get created or destroyed, the result
is a cyclic flow.
There are configurations resulting in flows with crossing edges,
as illustrated here.
In the second step,
the flow is simplified.
If there are crossing edges in the flow graph
we use local modifications to uncross them.
Bidirectional edges
are removed in a similar manner.
For the third step
consider a cyclic flow after preprocessing.
We decompose it into a set of cycles with a flow value of one.
We remove self-intersections and partition
the resulting set of cycles into clockwise and counterclockwise ordered cycles that are
processed separately.
We identify the union of the areas bounded by all cycles and remove the outer boundary
component of the covered area.
We repeat this peeling process until the entire flow graph is removed.
This yields
a tree-like structure
of nested cycles,
allowing us to compute a partitioning of the entire flow graph into subflows of value O(d).
In the fourth and final step of Phase I,
we realize a single subflow
by computing a crossing-free matching between incoming and outgoing robots for each tile.
By applying this technique iteratively, we realize a sequence of subflows as cyclic permutations of robots.
In the end, all robots are in their target tiles, after a total of O(d) steps.
Now we can proceed to Phase II:
In another O(d) moves, rotatesort delivers all robots to their target locations,
and we have achieved constant stretch.
The preceding description applies to robots at given grid positions.
What happens in more general configurations?
That depends on the proximity of robots.
If the robots are not too densely packed
here is what we can do.
There will be at most one robot per cell in an appropriate grid.
We move them
to appropriate grid positions, then apply the grid algorithm,
then move them to their target positions.
This achieves constant stretch.
For very densely packed disks
that cannot be well separated, no method can achieve
a stretch factor better than O of N to the 1/4th.
The proof considers the area of Voronoi cells during the
reconfiguration, showing that they must grow by a certain amount.
On the positive side, we establish a
stretch factor of O of square root of N even in this case.
The intricate difficulties of computing precise optimal solutions are demonstrated by the
seemingly simple case of just two disks, which is shown to be excruciatingly
difficult to solve to optimality.
These parallel motion schedules can be applied to real robots.
Here you see a number of examples.
Finally, here is a simulation of a bigger instance.
[music]
And with that, we are done!
For more infomation >> Что посмотреть на выходных – Хан Соло: Звёздные Войны. Истории. #ЧПНВ №16 - Duration: 4:03. 
For more infomation >> 노무현 전 대통령 9주기 추도식 평화의 시대와 함께 한다 - Duration: 6:34. 
For more infomation >> 溫暖的弦一心 張嘉倪老公大有來頭 竟和王思聰是好友 - Duration: 6:52. 
For more infomation >> Польша.Вроцлав.Тумский остров -You Tube. Poland.Wroclaw - Duration: 12:50. 
For more infomation >> 學財經的她卻走上演繹道路，一路高歌！最近一部溫暖的弦撩動人心 - Duration: 5:24. 
For more infomation >> 언론의 탈을 쓴 범죄 조폭 집단, 조선일보 그리고 거짓왜곡보도. - Duration: 5:33. 
For more infomation >> பெண்ணின் உயிரை பறித்த கைப்பை திக் திக் நிமிடங்கள் | KOLLYWOOD GOSSIPS - Duration: 1:10. 
For more infomation >> 마지막 길도 소탈했던 고 구본무 LG회장. - Duration: 1:35. 
For more infomation >> 《溫暖的弦》南弦這樣對待一心，溫暖直接無視 網友：真沉得住氣 - Duration: 3:50. 
Không có nhận xét nào:
Đăng nhận xét