I was wondering if there is any theory describing the decidability of a continuous pursuit-evasion game with constraints.

Two cars approach each other on a street with two lanes. Let's say one car is hostile and wants to cause a collision, while the other car tries to avoid one.

Sketch of scenario

Under the assumptions that:

  1. The cars cannot leave the street
  2. None of the cars can change directions (too dangerous with traffic). So in their coordinate system $v_x>0$
  3. There is a terminal velocity $v_T$ they can not exceed
  4. The acceleration and deceleration of both cars are limited. So $|\vec{a}| \in \left[a_B(v_x), a_F(|\vec{v}|) \right]$ where $a_B$ is a negative backward acceleration from breaking and $a_F$ a forward acceleration. Both would need to be dependent on velocity, otherwise $ v_x < 0$ or $ |\vec{v}| > v_T $ would be possible. Same for the other car with switched signs, e.g. assuming the cars are from the same model.

Would the hostile car always win? Is there some theory on that problem, or does a strategy come in your mind to avoid such collisions?

Example what I have in mind:
If you consider a more simple scenario in 1-d, drop assumption (2.) and allow for backward acceleration equal to forward acceleration the scenario should become decidable based on the initial distance and velocity of the cars. If the cars are very far apart the evading car can just accelerate to terminal velocity away from the pursuing car and it will never reach it. If they are to close it is obviously not possible to pull that move and it is only in the power of the pursuing car to cause or avoid a collision.

I was wondering if hostile cars are considered in current research on self-driving cars or if everything is based on a non-hostile environment and that question came to my mind.

  • $\begingroup$ Do you have any assumptions around reaction time? $\endgroup$ Commented Aug 30, 2021 at 10:06
  • $\begingroup$ I would say not. As this is just a "thought experiment" one could assume that at the moment the evading car notices that the other is hostile there are some initial conditions $(x_0,y_0)$,$(v_0,y_0)$ and no current acceleration. $\endgroup$
    – amh23
    Commented Aug 30, 2021 at 11:08
  • $\begingroup$ Welcome to Robotics amh23. On stack exchange, it is better to edit your answer to add information requested in comments, rather than adding more comments. Comments are for helping to improve questions and answers, and are distracting, so we try to keep them to a minimum. If all of the information needed to answer the question is contained within it, the comments can be tidied up (deleted). $\endgroup$
    – Ben
    Commented Sep 1, 2021 at 19:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.