The multi-agent surveillance problem is to find optimal trajectories of multiple agents that patrol a given area as evenly as possible. In this paper, we consider the multi-agent surveillance problem ...based on travel cost minimization. The surveillance area is given by an undirected graph. The penalty for each agent is introduced to evaluate the surveillance performance. Through a mixed logical dynamical system model, the multiagent surveillance problem is reduced to a mixed integer linear programming (MILP) problem. In model predictive control, trajectories of agents are generated by solving the MILP problem at each discrete time. Furthermore, a condition that the MILP problem is always feasible is derived based on the Chinese postman problem. Finally, the proposed method is demonstrated by a numerical example.
We analyze the cost allocation cooperative game, denoted by (N,ck), induced by the k-centrum Chinese Postman (k-centrum CP) delivery problem in connected undirected and strongly connected directed ...graphs. For the undirected case, we show, for example, that for k=1,2, (N,ck) is submodular for all graphs having non-negative edge-weights, for all locations of the post-office. For k≥3, we prove that (N,ck) is submodular for all non-negative edge-weights and for all locations of the post office if and only if the graph is either the cyclic graph on three edges or it is a graph wherein each edge is contained in at most one cycle and these cycles, if any, have only two edges. For the directed graph case we show, for example, that the k-centrum CP game induced by a strongly connected graph G is submodular for all k≥2 if and only if every arc in G is contained in precisely one directed cycle.
Belief Propagation (BP), a distributed, message-passing algorithm, has been widely used in different disciplines including information theory, artificial intelligence, statistics and optimization ...problems in graphical models such as Bayesian networks and Markov random fields. Despite BP algorithm has a great success in many application fields and many progress about BP algorithm has been made, the rigorous analysis about the correctness and convergence of BP algorithm are known in only a few cases for arbitrary graph. In this paper, we will investigate the correctness and convergence of BP algorithm for determining the optimal solutions of the Chinese postman problem in both undirected and directed graphs. As a main result, we prove that BP algorithm converges to the optimal solution of the undirected Chinese postman problem within
O
(
n
) iterations where
n
represents the number of vertices, provided that the optimal solution is unique. For the directed case, we consider the directed Chinese postman problem with capacity and show that BP algorithm also converges to its optimal solution after
O
(
n
) iterations, as long as its corresponding linear programming relaxation has the unique optimal solution.
Given an undirected graph G=(V,E;w,p), each edge e∈E has a weight w(e)∈R+ and a penalty p(e)∈R0+. We consider two types of restricted Chinese postman problems. The first problem is asked to find a ...tour C covering V, such that the value f(C)=w(C)+p(E∖C) is minimized. The second problem is asked to find a tour C covering V, such that the value h(C)=w(C)+pmax(E∖C) is minimized, where pmax(E∖C)=max{p(e)|e∈E∖C}. In the paper, we design some approximation algorithms to solve these problems.
We propose a polynomial algorithm computing a minimum plain-text representation of k-mer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model ...organisms or bacterial pangenomes, with only a minor runtime increase, we shrink the representation by up to 59% over unitigs and 26% over previous work. Additionally, the number of strings is decreased by up to 97% over unitigs and 90% over previous work. Finally, a small representation has advantages in downstream applications, as it speeds up SSHash-Lite queries by up to 4.26× over unitigs and 2.10× over previous work.
In this work, we introduce a multi-vehicle (or multi-postman) extension of the classical Mixed Rural Postman Problem, which we call the Min–Max Mixed Rural Postmen Cover Problem (MRPCP). The MRPCP is ...defined on a mixed graph
G
=
(
V
,
E
,
A
)
, where
V
is the vertex set,
E
denotes the (undirected) edge set and
A
represents the (directed) arc set. Let
F
⊆
E
(
H
⊆
A
) be the set of required edges (required arcs). There is a nonnegative weight associated with each edge and arc. The objective is to determine no more than
k
closed walks to cover all the required edges in
F
and all the required arcs in
H
such that the weight of the maximum weight closed walk is minimized. By replacing closed walks with (open) walks in the MRPCP, we obtain the Min–Max Mixed Rural Postmen Walk Cover Problem (MRPWCP). The Min–Max Mixed Chinese Postmen Cover Problem (MCPCP) is a special case of the MRPCP where
F
=
E
and
H
=
A
. The Min–Max Stacker Crane Cover Problem (SCCP) is another special case of the MRPCP where
F
=
∅
and
H
=
A
For the MRPCP with the input graph satisfying the weakly symmetric condition, i.e., for each arc there exists a parallel edge whose weight is not greater than this arc, we devise a
27
4
-approximation algorithm. This algorithm achieves an approximation ratio of
33
5
for the SCCP with the weakly symmetric condition. Moreover, we obtain the first 5-approximation algorithm (4-approximation algorithm) for the MRPWCP (MCPCP) with the weakly symmetric condition.
We investigate two min–max
k
-postmen cover problems. The first is the Min–Max Rural Postmen Cover Problem (RPC), in which we are given an undirected weighted graph and the objective is to find at ...most
k
closed walks, covering a required subset of edges, to minimize the weight of the maximum weight closed walk. The other is called the Min–Max Chinese Postmen Cover Problem, in which the goal is to find at most
k
closed walks, covering all the edges of an undirected weighted graph, to minimize the weight of the maximum weight closed walk. For both problems we propose the first constant-factor approximation algorithms with ratios 10 and 4, respectively. For the Metric RPC, a special case of the RPC with the edge weights obeying the triangle inequality, we obtain an improved 6-approximation algorithm by a matching-based approach. For the Min–Max Rural Postmen Walk Cover Problem (RPWC), a variant of the RPC with the closed walks replaced by (open) walks, we give a 5-approximation algorithm that improves on the previous 7-approximation algorithm. If
k
is fixed, we devise improved approximation algorithms for the Metric RPC and the RPWC with ratios
4
+
ϵ
and
3
+
ϵ
, respectively, where
ϵ
>
0
is an arbitrary small constant. The latter result improves on the existing
(
4
+
ϵ
)
-approximation algorithm. Moreover, we develop a
(
3
+
ϵ
)
-approximation algorithm for a special case of the RPC with fixed
k
, improving on the previous
(
4
+
ϵ
)
-approximation algorithm.
Multi-Agent Surveillance Based on Travel Cost Minimization MURAKATA, Kyohei; KOBAYASHI, Koichi; YAMASHITA, Yuh
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
2024/01/01, 2024-1-1, 20240101, Volume:
E107.A, Issue:
1
Journal Article
Peer reviewed
Open access
The multi-agent surveillance problem is to find optimal trajectories of multiple agents that patrol a given area as evenly as possible. In this paper, we consider the multi-agent surveillance problem ...based on travel cost minimization. The surveillance area is given by an undirected graph. The penalty for each agent is introduced to evaluate the surveillance performance. Through a mixed logical dynamical system model, the multi-agent surveillance problem is reduced to a mixed integer linear programming (MILP) problem. In model predictive control, trajectories of agents are generated by solving the MILP problem at each discrete time. Furthermore, a condition that the MILP problem is always feasible is derived based on the Chinese postman problem. Finally, the proposed method is demonstrated by a numerical example.
PDF
