# Multi-Agent Collision Simulator (Unicycle Kinematics) You are given $N$ agents moving in a 2D plane. Each agent is a disk of fixed radius and moves according to a simple **unicycle (differential-drive) motion model** with constant linear speed and constant yaw (turn) rate. Write a simulator that advances all agents in fixed timesteps and prints the **first time any two agents collide**, then stops. If no collision ever occurs within the simulation horizon, report that instead. ## Motion Model Each agent has a state $(x, y, \theta)$ — position in meters and heading in radians. With constant linear speed $v$ (m/s) and constant yaw rate $\omega$ (rad/s), one step of **forward Euler integration** over timestep $\Delta t$ is: $$x \mathrel{+}= v \cdot \cos(\theta) \cdot \Delta t$$ $$y \mathrel{+}= v \cdot \sin(\theta) \cdot \Delta t$$ $$\theta \mathrel{+}= \omega \cdot \Delta t$$ All agents advance one step together, using the same fixed $\Delta t = 0.01$ s. ## Collision Definition Each agent is a circle of fixed radius $r_i$. Two agents $i$ and $j$ **collide** when the Euclidean distance between their centers is less than or equal to the sum of their radii: $$\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \le r_i + r_j$$ (Touching counts as a collision.) Agents may already be overlapping at $t = 0$; this must be detected as a collision at time $0.00$. ## Input Each agent is described by six values: | Field | Type | Meaning | |-------|------|---------| | `x` | float | initial x position (meters) | | `y` | float | initial y position (meters) | | `theta` | float | initial heading (radians) | | `v` | float | constant linear speed (m/s) | | `omega` | float | constant yaw rate (rad/s) | | `r` | float | radius (meters) | The input is a list of $N$ agents, each given as the tuple `(x, y, theta, v, omega, r)`. The fixed timestep is $\Delta t = 0.01$ s. Simulate up to a horizon of $T_{\max} = 100.0$ s. ## Output - If a collision occurs, print exactly one line giving the simulated time of the **first** collision, formatted to two decimal places: ``` Collision occurred at 11.53 seconds ``` The simulated clock time at step $k$ is $k \times \Delta t$ (use multiplication, not accumulation, to avoid floating-point drift). A pre-existing overlap at $t = 0$ should be reported as `Collision occurred at 0.00 seconds`. - If no collision occurs by $T_{\max}$, print exactly: ``` No collision ``` When multiple pairs collide on the same step, any single collision time (which is identical for all of them) is correct — you only report the time, not which pair. ## Constraints - $1 \le N \le 500$ - Coordinates, speeds, and yaw rates are finite real numbers; radii are positive. - $\Delta t = 0.01$ s (fixed); $T_{\max} = 100.0$ s, so there are at most $10{,}000$ steps. - Check collisions over all unordered pairs $(i, j)$ with $i < j$ to avoid double-counting; the approach must extend naturally to all $N$ agents. ## Example Two agents on the x-axis moving toward each other: - Agent 0: `(x=0.0, y=0.0, theta=0.0, v=1.0, omega=0.0, r=0.5)` — at the origin, heading $+x$, moving right at 1 m/s. - Agent 1: `(x=9.15, y=0.0, theta=3.14159265, v=1.0, omega=0.0, r=0.5)` — at $x=9.15$, heading $-x$ (pointing toward agent 0), moving left at 1 m/s. The gap between centers starts at $9.15$ m and closes at $2$ m/s. The sum of radii is $r_0 + r_1 = 1.0$ m, so collision first occurs when the gap has closed by $9.15 - 1.0 = 8.15$ m. That takes $8.15 / 2 = 4.075$ s of real time, which falls between step 407 ($t = 4.07$ s, center distance $= 9.15 - 2 \times 4.07 = 1.01 > 1.0$, no collision) and step 408 ($t = 4.08$ s, center distance $= 9.15 - 2 \times 4.08 = 0.99 \le 1.0$, collision). Expected output: ``` Collision occurred at 4.08 seconds ```