Linear inequality constraints for Buffered Voronoi cells do not follow DCCP constraints? #2274

RandyChen233 · 2023-10-27T18:21:18Z

RandyChen233
Oct 27, 2023

Hi all,

I'm implementing a simple QP program based on buffered Voronoi cells as mentioned in Eqn. 3 in this paper . Below is my code:

from cvxpy import *
import numpy as np
from multiprocessing import Process, Pipe
from scipy import sparse
import matplotlib.pyplot as plt
import cvxpy as cp# Number of robots.
N = 3

#Discrete time horizon
T = 10

# x:(px,py,pz,vx,vy,vz)
# u:(ax,ay,az)
nx = 6 * N
nu = 3 * N

# Discrete time model of a double integrator (in R^3)

h = 0.1 #Discretization interval
Ad = sparse.csc_matrix([[1 ,0 ,0, h, 0, 0],
                        [0, 1 ,0, 0, h, 0],
                        [0, 0, 1, 0, 0, h],
                        [0, 0, 0, 1, 0, 0],
                        [0, 0, 0, 0, 1, 0],
                        [0, 0, 0, 0, 0, 1]])

Bd = sparse.csc_matrix([[h**2/2, 0, 0],
                        [0,h**2/2, 0],
                        [0 , 0, h**2/2],
                        [h, 0, 0],
                        [0, h, 0],
                        [0, 0, h]])

MAX_ITER_MPC = 35

# Initialize robot positions and goal positions randomly.
np.random.seed(0)
# robot_positions = np.random.rand(N, 3)  # Random initial positions.
goal_state = np.random.rand(N, 6)*2   # Random goal positions.
for i in range(goal_state.shape[0]):
  goal_state[i][3:] = np.zeros(3)

# ADMM variables.
x = Variable((nx, T+1))
u = Variable((nu, T))

# Formulate the model predictive control problem.
objective = 0

#Weight matrices in objective:
Q = sparse.diags([5, 5, 5, 1, 1, 1])
QN = Q*20
R = sparse.diags([0.1, 0.1, 0.1])

#Input constraint of each robot [(u_s, u_theta)]:
u_min = np.array([-2, -2, -2])
u_max = np.array([2,  2,  2])

#State constraint of each robot [(x, y, theta)]:
x_max = np.array([np.inf, np.inf, np.inf, 2, 2, 2])
x_min = np.array([-np.inf, -np.inf, -np.inf, -2, -2, -2])
x0 = np.array([0, 0, 1.1, 0, 0, 0, 
               -1.5, 0.6, 1.2, 0, 0, 0,
               -2, 3, 0.9, 0, 0, 0])
constr = [x[:,0] == x0] #Initial condition


state_dim = 6
input_dim = 3
r_min = 0.35

for i in range(N):
  for k in range(T):
      # Quadratic objective function: minimize distance to goal positions for each robot.
      objective += quad_form(x[:,k][i*state_dim:(i+1)*state_dim] - goal_state[i], Q) + quad_form(u[:, k][i*input_dim :(i+1)*input_dim ], R)
      # Additional constraints can be added here, e.g., collision avoidance, velocity constraints, etc.
      constr += [x[:,k][i*input_dim :(i+1)*input_dim ] <= u_max]
      constr += [x[:,k][i*input_dim :(i+1)*input_dim ] >= u_min]

      constr += [x[:,k][i*state_dim :(i+1)*state_dim ] <= x_max]
      constr += [x[:,k][i*state_dim :(i+1)*state_dim ] >= x_min]

      constr += [x[:,k+1][i*state_dim :(i+1)*state_dim] == Ad@x[:,k][i*state_dim :(i+1)*state_dim ] \
                                                              + Bd@u[:,k][i*input_dim:(i+1)*input_dim]]
                                                              
      #Buffered Voronoi Cells:
      for j in range(N):
        if j != i:
          p_i = x[:,k+1][i*state_dim:(i+1)*state_dim][:3] 
          p_j = x[:,k+1][j*state_dim:(j+1)*state_dim][:3]
          p_ij = p_j - p_i
          p_ji = p_i - p_j
          #TODO: fix this DCP error
          constr += [-1/2 * p_ji.T@p_ij + r_min * cp.norm(p_ij) <= 0]


  objective += quad_form(x[:, -1][i*state_dim :(i+1)*state_dim ] - goal_state[i], QN)

prox = Problem(Minimize(objective),constr)

prox.solve()

---------------------------------------------------------------------------
DCPError                                  Traceback (most recent call last)
[<ipython-input-25-60e97d315f35>](https://localhost:8080/#) in <cell line: 1>()
----> 1 prox.solve()

5 frames
[/usr/local/lib/python3.10/dist-packages/cvxpy/reductions/solvers/solving_chain.py](https://localhost:8080/#) in _reductions_for_problem_class(problem, candidates, gp, solver_opts)
    113             append += ("\nHowever, the problem does follow DQCP rules. "
    114                        "Consider calling solve() with `qcp=True`.")
--> 115         raise DCPError(
    116             "Problem does not follow DCP rules. Specifically:\n" + append)
    117     elif gp and not problem.is_dgp():

DCPError: Problem does not follow DCP rules. Specifically:
The following constraints are not DCP:
(var28[0:18, 1][0:6][0:3] + -(var28[0:18, 1][0:6][0:3] + var28[0:18, 1][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 1][6:12][0:3] + -var28[0:18, 1][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 1][6:12][0:3] + -var28[0:18, 1][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 1][0:6][0:3] + -(var28[0:18, 1][0:6][0:3] + var28[0:18, 1][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 1][6:12][0:3] + -var28[0:18, 1][0:6][0:3])
(var28[0:18, 1][0:6][0:3] + -(var28[0:18, 1][0:6][0:3] + var28[0:18, 1][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 1][12:18][0:3] + -var28[0:18, 1][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 1][12:18][0:3] + -var28[0:18, 1][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 1][0:6][0:3] + -(var28[0:18, 1][0:6][0:3] + var28[0:18, 1][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 1][12:18][0:3] + -var28[0:18, 1][0:6][0:3])
(var28[0:18, 2][0:6][0:3] + -(var28[0:18, 2][0:6][0:3] + var28[0:18, 2][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 2][6:12][0:3] + -var28[0:18, 2][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 2][6:12][0:3] + -var28[0:18, 2][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 2][0:6][0:3] + -(var28[0:18, 2][0:6][0:3] + var28[0:18, 2][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 2][6:12][0:3] + -var28[0:18, 2][0:6][0:3])
(var28[0:18, 2][0:6][0:3] + -(var28[0:18, 2][0:6][0:3] + var28[0:18, 2][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 2][12:18][0:3] + -var28[0:18, 2][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 2][12:18][0:3] + -var28[0:18, 2][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 2][0:6][0:3] + -(var28[0:18, 2][0:6][0:3] + var28[0:18, 2][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 2][12:18][0:3] + -var28[0:18, 2][0:6][0:3])
(var28[0:18, 3][0:6][0:3] + -(var28[0:18, 3][0:6][0:3] + var28[0:18, 3][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 3][6:12][0:3] + -var28[0:18, 3][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 3][6:12][0:3] + -var28[0:18, 3][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 3][0:6][0:3] + -(var28[0:18, 3][0:6][0:3] + var28[0:18, 3][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 3][6:12][0:3] + -var28[0:18, 3][0:6][0:3])
(var28[0:18, 3][0:6][0:3] + -(var28[0:18, 3][0:6][0:3] + var28[0:18, 3][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 3][12:18][0:3] + -var28[0:18, 3][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 3][12:18][0:3] + -var28[0:18, 3][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 3][0:6][0:3] + -(var28[0:18, 3][0:6][0:3] + var28[0:18, 3][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 3][12:18][0:3] + -var28[0:18, 3][0:6][0:3])
(var28[0:18, 4][0:6][0:3] + -(var28[0:18, 4][0:6][0:3] + var28[0:18, 4][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 4][6:12][0:3] + -var28[0:18, 4][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 4][6:12][0:3] + -var28[0:18, 4][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 4][0:6][0:3] + -(var28[0:18, 4][0:6][0:3] + var28[0:18, 4][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 4][6:12][0:3] + -var28[0:18, 4][0:6][0:3])
(var28[0:18, 4][0:6][0:3] + -(var28[0:18, 4][0:6][0:3] + var28[0:18, 4][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 4][12:18][0:3] + -var28[0:18, 4][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 4][12:18][0:3] + -var28[0:18, 4][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 4][0:6][0:3] + -(var28[0:18, 4][0:6][0:3] + var28[0:18, 4][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 4][12:18][0:3] + -var28[0:18, 4][0:6][0:3])
(var28[0:18, 5][0:6][0:3] + -(var28[0:18, 5][0:6][0:3] + var28[0:18, 5][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 5][6:12][0:3] + -var28[0:18, 5][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 5][6:12][0:3] + -var28[0:18, 5][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 5][0:6][0:3] + -(var28[0:18, 5][0:6][0:3] + var28[0:18, 5][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 5][6:12][0:3] + -var28[0:18, 5][0:6][0:3])
(var28[0:18, 5][0:6][0:3] + -(var28[0:18, 5][0:6][0:3] + var28[0:18, 5][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 5][12:18][0:3] + -var28[0:18, 5][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 5][12:18][0:3] + -var28[0:18, 5][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 5][0:6][0:3] + -(var28[0:18, 5][0:6][0:3] + var28[0:18, 5][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 5][12:18][0:3] + -var28[0:18, 5][0:6][0:3])
(var28[0:18, 6][0:6][0:3] + -(var28[0:18, 6][0:6][0:3] + var28[0:18, 6][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 6][6:12][0:3] + -var28[0:18, 6][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 6][6:12][0:3] + -var28[0:18, 6][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 6][0:6][0:3] + -(var28[0:18, 6][0:6][0:3] + var28[0:18, 6][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 6][6:12][0:3] + -var28[0:18, 6][0:6][0:3])
(var28[0:18, 6][0:6][0:3] + -(var28[0:18, 6][0:6][0:3] + var28[0:18, 6][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 6][12:18][0:3] + -var28[0:18, 6][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 6][12:18][0:3] + -var28[0:18, 6][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 6][0:6][0:3] + -(var28[0:18, 6][0:6][0:3] + var28[0:18, 6][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 6][12:18][0:3] + -var28[0:18, 6][0:6][0:3])
(var28[0:18, 7][0:6][0:3] + -(var28[0:18, 7][0:6][0:3] + var28[0:18, 7][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 7][6:12][0:3] + -var28[0:18, 7][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 7][6:12][0:3] + -var28[0:18, 7][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 7][0:6][0:3] + -(var28[0:18, 7][0:6][0:3] + var28[0:18, 7][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 7][6:12][0:3] + -var28[0:18, 7][0:6][0:3])
(var28[0:18, 7][0:6][0:3] + -(var28[0:18, 7][0:6][0:3] + var28[0:18, 7][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 7][12:18][0:3] + -var28[0:18, 7][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 7][12:18][0:3] + -var28[0:18, 7][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 7][0:6][0:3] + -(var28[0:18, 7][0:6][0:3] + var28[0:18, 7][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 7][12:18][0:3] + -var28[0:18, 7][0:6][0:3])
(var28[0:18, 8][0:6][0:3] + -(var28[0:18, 8][0:6][0:3] + var28[0:18, 8][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 8][6:12][0:3] + -var28[0:18, 8][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 8][6:12][0:3] + -var28[0:18, 8][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 8][0:6][0:3] + -(var28[0:18, 8][0:6][0:3] + var28[0:18, 8][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 8][6:12][0:3] + -var28[0:18, 8][0:6][0:3])
(var28[0:18, 8][0:6][0:3] + -(var28[0:18, 8][0:6][0:3] + var28[0:18, 8][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 8][12:18][0:3] + -var28[0:18, 8][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 8][12:18][0:3] + -var28[0:18, 8][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 8][0:6][0:3] + -(var28[0:18, 8][0:6][0:3] + var28[0:18, 8][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 8][12:18][0:3] + -var28[0:18, 8][0:6][0:3])
(var28[0:18, 9][0:6][0:3] + -(var28[0:18, 9][0:6][0:3] + var28[0:18, 9][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 9][6:12][0:3] + -var28[0:18, 9][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 9][6:12][0:3] + -var28[0:18, 9][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 9][0:6][0:3] + -(var28[0:18, 9][0:6][0:3] + var28[0:18, 9][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 9][6:12][0:3] + -var28[0:18, 9][0:6][0:3])
(var28[0:18, 9][0:6][0:3] + -(var28[0:18, 9][0:6][0:3] + var28[0:18, 9][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 9][12:18][0:3] + -var28[0:18, 9][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 9][12:18][0:3] + -var28[0:18, 9][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 9][0:6][0:3] + -(var28[0:18, 9][0:6][0:3] + var28[0:18, 9][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 9][12:18][0:3] + -var28[0:18, 9][0:6][0:3])
(var28[0:18, 10][0:6][0:3] + -(var28[0:18, 10][0:6][0:3] + var28[0:18, 10][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 10][6:12][0:3] + -var28[0:18, 10][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 10][6:12][0:3] + -var28[0:18, 10][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 10][0:6][0:3] + -(var28[0:18, 10][0:6][0:3] + var28[0:18, 10][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 10][6:12][0:3] + -var28[0:18, 10][0:6][0:3])
(var28[0:18, 10][0:6][0:3] + -(var28[0:18, 10][0:6][0:3] + var28[0:18, 10][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 10][12:18][0:3] + -var28[0:18, 10][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 10][12:18][0:3] + -var28[0:18, 10][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 10][0:6][0:3] + -(var28[0:18, 10][0:6][0:3] + var28[0:18, 10][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 10][12:18][0:3] + -var28[0:18, 10][0:6][0:3])
(var28[0:18, 1][0:6][0:3] + -(var28[0:18, 1][0:6][0:3] + var28[0:18, 1][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 1][6:12][0:3] + -var28[0:18, 1][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 1][6:12][0:3] + -var28[0:18, 1][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 1][0:6][0:3] + -(var28[0:18, 1][0:6][0:3] + var28[0:18, 1][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 1][6:12][0:3] + -var28[0:18, 1][0:6][0:3])
(var28[0:18, 1][0:6][0:3] + -(var28[0:18, 1][0:6][0:3] + var28[0:18, 1][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 1][12:18][0:3] + -var28[0:18, 1][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 1][12:18][0:3] + -var28[0:18, 1][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 1][0:6][0:3] + -(var28[0:18, 1][0:6][0:3] + var28[0:18, 1][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 1][12:18][0:3] + -var28[0:18, 1][0:6][0:3])
(var28[0:18, 2][0:6][0:3] + -(var28[0:18, 2][0:6][0:3] + var28[0:18, 2][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 2][6:12][0:3] + -var28[0:18, 2][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 2][6:12][0:3] + -var28[0:18, 2][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 2][0:6][0:3] + -(var28[0:18, 2][0:6][0:3] + var28[0:18, 2][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 2][6:12][0:3] + -var28[0:18, 2][0:6][0:3])
(var28[0:18, 2][0:6][0:3] + -(var28[0:18, 2][0:6][0:3] + var28[0:18, 2][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 2][12:18][0:3] + -var28[0:18, 2][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 2][12:18][0:3] + -var28[0:18, 2][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 2][0:6][0:3] + -(var28[0:18, 2][0:6][0:3] + var28[0:18, 2][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 2][12:18][0:3] + -var28[0:18, 2][0:6][0:3])
(var28[0:18, 3][0:6][0:3] + -(var28[0:18, 3][0:6][0:3] + var28[0:18, 3][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 3][6:12][0:3] + -var28[0:18, 3][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 3][6:12][0:3] + -var28[0:18, 3][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 3][0:6][0:3] + -(var28[0:18, 3][0:6][0:3] + var28[0:18, 3][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 3][6:12][0:3] + -var28[0:18, 3][0:6][0:3])
(var28[0:18, 3][0:6][0:3] + -(var28[0:18, 3][0:6][0:3] + var28[0:18, 3][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 3][12:18][0:3] + -var28[0:18, 3][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 3][12:18][0:3] + -var28[0:18, 3][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 3][0:6][0:3] + -(var28[0:18, 3][0:6][0:3] + var28[0:18, 3][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 3][12:18][0:3] + -var28[0:18, 3][0:6][0:3])
(var28[0:18, 4][0:6][0:3] + -(var28[0:18, 4][0:6][0:3] + var28[0:18, 4][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 4][6:12][0:3] + -var28[0:18, 4][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 4][6:12][0:3] + -var28[0:18, 4][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 4][0:6][0:3] + -(var28[0:18, 4][0:6][0:3] + var28[0:18, 4][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 4][6:12][0:3] + -var28[0:18, 4][0:6][0:3])
(var28[0:18, 4][0:6][0:3] + -(var28[0:18, 4][0:6][0:3] + var28[0:18, 4][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 4][12:18][0:3] + -var28[0:18, 4][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 4][12:18][0:3] + -var28[0:18, 4][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 4][0:6][0:3] + -(var28[0:18, 4][0:6][0:3] + var28[0:18, 4][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 4][12:18][0:3] + -var28[0:18, 4][0:6][0:3])
(var28[0:18, 5][0:6][0:3] + -(var28[0:18, 5][0:6][0:3] + var28[0:18, 5][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 5][6:12][0:3] + -var28[0:18, 5][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 5][6:12][0:3] + -var28[0:18, 5][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 5][0:6][0:3] + -(var28[0:18, 5][0:6][0:3] + var28[0:18, 5][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 5][6:12][0:3] + -var28[0:18, 5][0:6][0:3])
(var28[0:18, 5][0:6][0:3] + -(var28[0:18, 5][0:6][0:3] + var28[0:18, 5][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 5][12:18][0:3] + -var28[0:18, 5][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 5][12:18][0:3] + -var28[0:18, 5][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 5][0:6][0:3] + -(var28[0:18, 5][0:6][0:3] + var28[0:18, 5][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 5][12:18][0:3] + -var28[0:18, 5][0:6][0:3])
(var28[0:18, 6][0:6][0:3] + -(var28[0:18, 6][0:6][0:3] + var28[0:18, 6][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 6][6:12][0:3] + -var28[0:18, 6][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 6][6:12][0:3] + -var28[0:18, 6][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 6][0:6][0:3] + -(var28[0:18, 6][0:6][0:3] + var28[0:18, 6][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 6][6:12][0:3] + -var28[0:18, 6][0:6][0:3])
(var28[0:18, 6][0:6][0:3] + -(var28[0:18, 6][0:6][0:3] + var28[0:18, 6][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 6][12:18][0:3] + -var28[0:18, 6][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 6][12:18][0:3] + -var28[0:18, 6][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 6][0:6][0:3] + -(var28[0:18, 6][0:6][0:3] + var28[0:18, 6][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 6][12:18][0:3] + -var28[0:18, 6][0:6][0:3])
(var28[0:18, 7][0:6][0:3] + -(var28[0:18, 7][0:6][0:3] + var28[0:18, 7][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 7][6:12][0:3] + -var28[0:18, 7][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 7][6:12][0:3] + -var28[0:18, 7][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 7][0:6][0:3] + -(var28[0:18, 7][0:6][0:3] + var28[0:18, 7][6:12][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 7][6:12][0:3] + -var28[0:18, 7][0:6][0:3])
(var28[0:18, 7][0:6][0:3] + -(var28[0:18, 7][0:6][0:3] + var28[0:18, 7][12:18][0:3]) / Promote(2.0, (3,))) @ (var28[0:18, 7][12:18][0:3] + -var28[0:18, 7][0:6][0:3]) + 0.35 @ Pnorm(var28[0:18, 7][12:18][0:3] + -var28[0:18, 7][0:6][0:3], 2) <= 0.0 , because the following subexpressions are not:
|--  (var28[0:18, 7][0:6][0:3] + -(var28[0:18, 7][0:6][0:3] + var28[0:18, 7][
.....

I wonder how this linear inequality constraint results in DCCP error?

Answered by SteveDiamond

Oct 27, 2023

This is still not linear if p is a variable. Though I don't understand the notation fully.

View full answer

SteveDiamond · 2023-10-27T19:14:23Z

SteveDiamond
Oct 27, 2023
Maintainer

How is this linear? p_ji.T@p_ij is a non-linear term.

          p_i = x[:,k+1][i*state_dim:(i+1)*state_dim][:3] 
          p_j = x[:,k+1][j*state_dim:(j+1)*state_dim][:3]
          p_ij = p_j - p_i
          p_ji = p_i - p_j
          #TODO: fix this DCP error
          constr += [-1/2 * p_ji.T@p_ij + r_min * cp.norm(p_ij) <= 0]

2 replies

RandyChen233 Oct 27, 2023
Author

Thanks for the response, I think I used the wrong version of the equation. In its original form, the Buffered voronoi cell is given as:

I actually tried using this version, but the same error arose. Does CVXPY not accept this constraint in its crude form?

SteveDiamond Oct 27, 2023
Maintainer

This is still not linear if p is a variable. Though I don't understand the notation fully.

Answer selected by RandyChen233

goulart-paul · 2023-10-28T09:17:41Z

goulart-paul
Oct 28, 2023

I did not read the paper in great detail, but it seems to me that you are trying to implement "Problem 1"in §3.A of the paper by directly encoding the buffered voronoi cell (BVC) constraint, specifically (8) in the paper.

The paper does not advocate doing that though. Instead, it suggests reformulating (8) using the linear inequality (12).

1 reply

RandyChen233 Nov 8, 2023
Author

Thanks! I wonder how this reformulation can be achieved? I tried deriving the linear inequality in (12) but I didn't end up getting this clean equation

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Linear inequality constraints for Buffered Voronoi cells do not follow DCCP constraints? #2274

{{title}}

Replies: 2 comments 3 replies

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

Select a reply

Linear inequality constraints for Buffered Voronoi cells do not follow DCCP constraints? #2274

RandyChen233 Oct 27, 2023

Replies: 2 comments · 3 replies

SteveDiamond Oct 27, 2023 Maintainer

RandyChen233 Oct 27, 2023 Author

SteveDiamond Oct 27, 2023 Maintainer

goulart-paul Oct 28, 2023

RandyChen233 Nov 8, 2023 Author

RandyChen233
Oct 27, 2023

Replies: 2 comments 3 replies

SteveDiamond
Oct 27, 2023
Maintainer

RandyChen233 Oct 27, 2023
Author

SteveDiamond Oct 27, 2023
Maintainer

goulart-paul
Oct 28, 2023

RandyChen233 Nov 8, 2023
Author