2
$\begingroup$

SourceDataFile

So i am attempting to optimize the following pointing problem. I have a set of sensors (cameras) and a set of targets. Each camera can be oriented directly at one one target, but based on its FOV it may see multiple targets. The goal is to cover as many targets as possible with the user defined number of cameras (i.e stereo, 2)

I initially took the approach of using MATLAB and intlinprog and will show the formulation, but seeing as I am new to MILP I am open to criticism and suggestions

Problem formulation

Given:

  1. S sensors
  2. T targets
  3. P pointing options for each S sensor
  4. T == P
  5. R required coverage level (i.e 2 for stereo or 1 for mono)

Problem Structure:

The source data for the problem is logical/binary 3D array called Vis (P x T x S) indexed (i,j,k)

  1. Each Layer (3rd Dimension S) represents a camera
  2. Each Row in a layer represents a pointing option
  3. The column in a given row and layer is true if that target is seen

Vis (i,j,k) = true if Camera(k) can see target (j) using pointing option (i)

Constraints:

  1. Each camera can be assigned only one pointing option

Goal: Maximize the number of targets that have atleast the requried coverage level.

I am going to insert an example of my code below. Some notes are that I take the matrix of Vis and convert it to a 2-D array by concating each "layer" alond the first dimension.

There is a binary decision variable for each pointing option for each camera and a binary switching variable used to switch for the optimizing the number of targets with the desired coverage level.

S = 156; %100 Cameras
T = 100; %100 Targets
P = T;   %100 Pointing options

R = 2;  % Required Coverage Level (stereo)

% Load Vis Matrix it is (P x T X S)
%When the matrix is very scattered the solver works fine, the problem is
%a few cameras can see alot of targets and some can see none

load('Vis.mat');

%Use permute and reshape matrix so that each "3rd" dimension layer is
%concated onton the bottom of the previous one
VisNew = permute(Vis,[1 3 2]);
VisNew = reshape(VisNew,[],size(Vis,2),1);

[m,n] = size(VisNew);

%% Optimization Problem Setup
%The first set of variables will be the logical t/f for the pointing
%option's (m) . The last set of Logic t/f will be the coverage variables (n)
NumVars = m + n;

% All variables are integers
prob_struct.intcon = 1:NumVars;

% All Variables have lb of 0 and ub of 1
prob_struct.lb = zeros(NumVars,1);
prob_struct.ub = ones(NumVars,1);

% The "maximization" (min for the function) is the sum of the "Required
% Coverage" switching variables which are only true if the required
% coverage is obtained
prob_struct.f = [zeros(m,1); -1*ones(n,1)];

%The equality constraint comes from that each camera can only
%be tasked 1 pointing option. So the sum of those options variables for each
%camera should sum to 1
prob_struct.Aeq = zeros(S,NumVars);
for x = 1:S
    prob_struct.Aeq(x,((x-1)*P+1:x*P)) = 1;
end
prob_struct.beq = ones(S,1);

% The inequality constraint is just ensuring that the coverage
% variable is only switched when there is enough coverage for that target
prob_struct.Aineq = [VisNew'.*-1 R.*eye(n)];

prob_struct.bineq = zeros(n,1);

% Define which solver to use
prob_struct.solver = 'intlinprog';
prob_struct.options = optimoptions('intlinprog');

%Solve the problem
[X,Y] = intlinprog(prob_struct);

$\endgroup$
  • 1
    $\begingroup$ I didn't read your code, but if you are just looking for a comment about whether MILP is the right approach here, I would say yes, it is. This seems like a variant of the classical set covering problem, which is often solved via IP. $\endgroup$ – LarrySnyder610 May 22 at 20:48
  • $\begingroup$ I was looking more for general input on if there is a better approach. I provided the code for more clarification on the problem setup an incase anyone wanted to look at it. I will take a look at the set covering problem $\endgroup$ – S moran May 23 at 0:58
  • $\begingroup$ To be clear, I’m not saying your problem is set covering. Just some further evidence that MILP is a reasonable approach here. $\endgroup$ – LarrySnyder610 May 23 at 3:08
  • $\begingroup$ I suspect you might get more eyeballs on the question if you wrote your formulation in mathematical notation rather than in MATLAB syntax (which is harder to read for those of us who do not use MATLAB). $\endgroup$ – prubin May 23 at 19:48
  • $\begingroup$ Agreed — you can take advantage of MathJax. $\endgroup$ – LarrySnyder610 May 24 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.