2

Let $\mathcal{S}\subseteq\mathbb{R}^n$ be a set of an inaccessible area. We consider the time as $\{\ldots,~ t-1,~ t,~ t+1,~ \ldots\}$. We assume that a position of a point at time $t$ is given as $x\in\mathbb{R}^n$, and its position will be changed to $x+v$ at time $t+1$. (linearly move) However, the point must not enter the area $\mathcal{S}$.

Let me introduce an example.

1

The amount of the change of position should be reduced because the point cannot enter the area $\mathcal{S}$. Thus, the position at $t+1$ will be like the following.

image 2

I want to express this problem in mathematically.

\begin{array}{cl} c & = & \displaystyle\max_{0 \le c \le 1} & c\\ && \text{subject to} & x+c'v \notin \mathcal{S},\quad\forall c'\in[0,c] \end{array}

I express the problem like the above. However, $c$ is the objective function (as a constant function), and $c$ is also in the range for the constraint (as $[0,c]$). Is there any nice expression for this problem?

In addition, I cannot solve this problem using MATLAB because the term of $\forall c' \in [0,c]$. Actually, I am running an algorihtm substituting $c$ into $0.1,~0.2,~\ldots,~0.9,~1.0$ and choosing one. Please let me know some packages or algorithms for solving this problem if you know. Thank you.

Danny_Kim
  • 3,423
  • Just to be clear: $v$ is given, correct? And how bad is $S$? Is it a convex set (you drew a nonconvex one)? – max_zorn Jan 10 '18 at 04:00
  • @max_zorn Yes, $v$ is given in this case, and $\mathcal{S}$ is either convex or non-convex. Actually the set $\mathcal{S}$ is the union of a number of $n$-dimmensional balls. The center and radius of each ball are given. – Danny_Kim Jan 10 '18 at 04:01
  • 1
    If you don't want $c$ to appear in $\forall c' \in [0,c]$ you can replace the constraint with $x+tcv \not\in S \ \forall t\in[0,1]$. However, you may still not be able to solve it in Matlab because of the $\forall$. This is essentially a ray-shape intersection problem, and efficient techniques depend on how the shape is specified and what properties you know about it. –  Jan 10 '18 at 04:06
  • @Rahul The problem becomes a problem to maximize $c$ over $[0,1]$ subject to $x+tcv \notin \mathcal{S}$ for all $t\in[0,1]$. Wow, I will change my problem like this. I felt very strange because $c$ is in the objective function as well as in constraint range. – Danny_Kim Jan 10 '18 at 04:11
  • 1
    Solve the problem for each ball, say centred at $c$ with radius $r$. Write down $|x+tv-c|=r^2$. Expand the norm squared term. This gives you a quadratic in $t$ that you can solve. Try both solutions and store the smaller positive $t$. Do this for all balls and take the minimal $t$. I am assuming that you are in none of the balls here. – max_zorn Jan 10 '18 at 04:17
  • @max_zorn Thank you, I will try that – Danny_Kim Jan 10 '18 at 04:20
  • @Danny_Kim, where did the problem show up? Please leave a reference if it is publicly available. – max_zorn Jan 10 '18 at 04:22
  • @max_zorn This is not a public problem in the textbook. I am making some problems myself explaining a reasonable situation. For example, there are $30$ robots. Each robot can see an area with radius $10$ meters. In this case, John should get to the destination point. (Source point and Destination point are given.) John can move 10 meters each time and cannot change the direction. How can John reach the destination point as fast as possible without being detected by the robots. – Danny_Kim Jan 10 '18 at 04:27
  • @Danny_Kim, cool - good luck! – max_zorn Jan 10 '18 at 05:41
  • Won't just replacing $\max\limits{0\le c\le 1}(x),x+c'v\notin S,\forall c'\in[0,c]$ into $\max(c'),x+c'v\notin S,c'\le 1$ work? By setting $x+c'v\notin S$ we are getting $c'\in[-k,\ell]$, by saying $c'\le 1$ we are getting $c'\in[-k,\min(\ell,1)]$ and when taking the max we get: $\max(c'),x+c'v\notin S,c'\le 1=\max[-k,\min(\ell,1)]=\min(\ell,1)$. We also know that $\ell\ge0$ because assuming the $x\notin S$ we have $x+0v\notin S$. Sorry if i missed something and this is wrong – ℋolo Jan 10 '18 at 06:14

0 Answers0