Algorithm for Optimal Chance Constrained Knapsack Problem with Applications to Multi-Robot Teaming
Algorithm for Optimal Chance Constrained Knapsack Problem with Applications to Multi-Robot Teaming
复制标题
最优机会约束背包问题算法及其在多机器人协作中的应用
DOI：
10.1109/icra.2018.8461040
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
N. Chakraborty
中科院分区：
文献类型：
--
作者：
F. Yang;N. Chakraborty
受多机器人团队选择应用的启发，本文提出了一种计算机会约束0-1背包问题最优解的新算法。在背包问题的这种变化中，目标函数是确定性的，但项目的权重是随机的，因此背包约束是随机的。我们将机会约束背包问题转换为方差均值平面上的二维离散优化问题，其中平面上的每个点都可以通过将项目分配给背包来识别。利用机会约束背包问题在方差-均值平面上的非凸可行域的几何性质，提出了一种新的确定性方法，通过求解一系列确定性背包问题（称为风险厌恶背包问题）来寻找最优解.我们将我们的算法应用于多机器人团队选择问题，以覆盖给定的路线，其中路线的长度远大于每个机器人可以飞行的长度，并且单个机器人可以飞行的长度是随机变量（具有已知的均值和方差）。我们提出了随机生成的数据的模拟结果，以证明我们的方法是可扩展的机器人的数量和增加的不确定性的距离，一个单独的机器人可以旅行。
Motivated by applications in multirobot team selection, in this paper, we present a novel algorithm for computing optimal solution of chance-constrained 0–1 knapsack problem. In this variation of the knapsack problem, the objective function is deterministic but the weights of the items are stochastic and therefore the knapsack constraint is stochastic. We convert the chance-constrained knapsack problem to a two-dimensional discrete optimization problem on the variance-mean plane, where each point on the plane can be identified with an assignment of items to the knapsack. By exploiting the geometry of the non-convex feasible region of the chance-constrained knapsack problem in the variance-mean plane, we present a novel deterministic technique to find an optimal solution by solving a sequence of deterministic knapsack problems (called risk-averse knapsack problem). We apply our algorithm to a multirobot team selection problem to cover a given route, where the length of the route is much larger than the length each individual robot can fly and the length that an individual robot can fly is a random variable (with known mean and variance). We present simulation results on randomly generated data to demonstrate that our approach is scalable with both the number of robots and increasing uncertainty of the distance an individual robot can travel.