How can I treat a problem like a search problem in AI?
To treat it as a search problem, you should have a decision tree in mind. In your example, the each node's degree would be the total combination of possible movements for each car (except for the combination in which all cars stay put). Then, each edge of the decision tree would represent a transition from one timestep to the next and each node would represent the positions of all the vehicles at that timestep. One can use the current depth of the tree during the search process to track the current timestep. Using this setup, there are many possible tree search algorithms that may suffice for your problem.