The *traffic network of Dubins cars* domain involves navigation in a small network of
two-lane roads with vehicles that have Dubins car dynamics. There is an
adversary that selects the motion of other cars. The adversary is subject to
assumptions such as obeying traffic rules and not parking unfairly at locations
that must be eventually reached by the controller.

All cars including the controlled robot are assumed to have the same rigid body
shape and to have the same dynamics. Let \( \mathcal I \) be the index set for the
cars in the network, with \( r \) denoting the index of the controlled robot; all
cars indexed with \( i \in {\mathcal I}\backslash\{r\} \) are regarded as a part of
the (adversarial) environment.
The pose of each car \( i \in {\mathcal I} \) is specified by \( (x_i,y_i,\theta_i) \),
where \( (x_i,y_i)\in \mathbb{R}^2 \) is referred to as *position*, and
\( \theta_i \in S^1 \) is referred to as *orientation*. The car's body is a
rectangle or a circle, and the position is defined to be at the mean point
(center of mass) of the body. Let \( w \) be the width of the car -- this is
identical for each \( i \in {\mathcal I} \).
The trajectories of car \( i \) are solutions of
\begin{align}
\dot{x_i} &= u_i \cos \theta_i \\
\dot{y_i} &= u_i \sin \theta_i \\
\dot{\theta_i} &= \omega_i
\end{align}
where the control inputs are constrained as \( \lvert u_i(t) \rvert \leq u_{\mathrm{max}} \) and
\( \lvert\omega_i(t)\rvert \leq \omega_{\mathrm{max}} \).
The workspace is a randomly generated road network constructed as follows.
Create a planar graph \( G = (V,E) \) in which each vertex \( v \) has degree \( d_v \le 4 \)
(i.e., at most 4 neighbors). Embed this graph in the plane, and expand the
edges to have width \( 4w \) (recall \( w \) is the common vehicle width).
For this aspect of the "traffic network of Dubins cars" problem domain, we are
able to vary the bounds \( u_{\mathrm{max}} \) and \( \omega_{\mathrm{max}} \) on the
permissible control inputs, the size (\( |V| \)) and topology (\( |E| \)) of the road
network, and the number of other cars, i.e. \( |\mathcal I| \).

Because there is now an environment that may behave adversarially, task specifications are of the form \( \varphi_{\mathrm{env}} \Rightarrow \varphi_{\mathrm{sys}} \), where \( \varphi_{\mathrm{env}} \) is known as the "assumption" and \( \varphi_{\mathrm{sys}} \) as the "guarantee." The desired behaviors to be realized by the robot are provided through \( \varphi_{\mathrm{sys}} \) and include

- obstacle avoidance while repeatedly visiting regions of interest, as in \begin{equation} q(0) = \mathrm{init} \wedge \Galways \left( q(t) \notin \mathrm{Obs} \right) \wedge \bigwedge_{i} \Galways \Feventually \mathrm{goal}_i \end{equation}
- remaining in the right-lane except when it is blocked;
- stopping at intersections, which are treated as all-ways stops, and then proceeding based on order of arrival.