Forcing non-ego car(s) to switch lanes at some time step

[TheNeeloy]

Hi @eleurent , awesome project!

I am developing a highway environment where sometimes an exit ramp will appear. I created a graph similar to the merge environment you developed, but instead of an on ramp, I created an exit ramp.

Visually, this is what a portion of the highway looks like:

In my highway environment, lanes where cars can merge left and right are named similarly. For example in the image above, there are three nodes named "A" and three nodes named "B" denoting the start and end of three portions of lanes. This is following the same format of the _make_road() function of merge_env.py. My understanding is that there are three nodes created indexed by [0,1,2] when a node is added to the road graph with the same name.

I see there is a ControlledVehicle.plan_route_to() function which takes in the string name of a destination node you want a car to drive to, and will set the route of the vehicle to reach that goal. I don't think this function considers a specific lane you would like the car to end up in (e.g. as long as the B string node is reached, it doesn't matter if the car reached B0 or B1 or B2 index)

Is there a way to force a non-ego vehicle (IDMVehicle object) to switch lanes at a specific timestep? For example, is there a way to force the blue car in the picture above to merge right from the [A0,B0] lane to the [A1,B1] lane?

Actually, I also just saw that IDM vehicles have a change_lane_policy() function that sets a target_lane_index variable for the car. Is there a good function I can set the target_lane_index variable of a non-ego vehicle from the environment python file so that the ego vehicle switches lanes to my target lane at the next IDMVehicle.act() call?

Truly appreciate your time and help, and please feel free to let me know if I can clarify any details from my end. In the meantime, I'll try setting the target_lane_index variable from my environment file and seeing if it works.

[eleurent]

Hi @TheNeeloy, I think you have a very good understanding of what's going on, but here's a a small clarification to make sure we are on the same page.

My understanding is that there are three nodes created indexed by [0,1,2] when a node is added to the road graph with the same name.

I would say that there are two nodes, A and B, but they are connected by three edges: (A,B,0) (A,B,1), (A,B,2).

In fact, my (flawed) reasoning when I wrote this model was that the lanes were not really relevant to route planning (since you can freely change lane on a highway without really changing your planned route), but rather the road segments (set of adjacent lanes) were. But it is quite simplistic, and although it turned out fine for most situations, it is not great for your scenario since it does not really allow to plan in the lane space (and thus plan a lane change). The current solution only takes decisions at the end of a road segment, by selecting the next one in the planned route and tracking it instead.

Maybe we would need to adapt it to actually account for the lane changes in the plan (eg (A,B,0) -> (A,B,1) -> (A,B,2) -> (B,C,0)), which could probably be achieved by duplicating the node as you suggested. But then, we are coupling again the lanes vs road segment decisions, which does not really give the liberty to change lane freely.

A possible solution related to what you suggested:

Actually, I also just saw that IDM vehicles have a change_lane_policy() function that sets a target_lane_index variable for the car. Is there a good function I can set the target_lane_index variable of a non-ego vehicle from the environment python file so that the ego vehicle switches lanes to my target lane at the next IDMVehicle.act() call?

Something in this spirit already exists: a planned route is currently a list of lane indexes (node_from, node_to, lane_id). If I remember correctly, the lane_id is set to None by default, which means the vehicle is indifferent to the actual lane. But if it is set to an actual lane_id, then this lane will be chosen either when changing of road segment in follow_road() as usual, but also if the vehicle is driving in a lane adjacent to its target lane.

So in your example, if a vehicle has a route [(A, B, 2), (B, C, 0)], they will change lane if they are on (A, B, 1). However, since this is only a local decision it won't work if the vehicle starts in (A, B, 0). It would need to be part of the planning procedure to anticipate two lane changes (A, B, 0) -> (A, B, 1) -> (A, B, 2).

I'm not sure what is the best way to go. Maybe the easiest would be to just adapt this rule and move to an adjacent lane if it gets you closer to a target lane (ie same road segment but closer lane_id), rather than exactly on the correct lane_id.

[eleurent]

Actually, as I'm reading this code again, it seems that it already does what we want: do a lane change if it is safe and if it goes in the good direction (change of lane id has the same sign as desired change of lane id)

        # Do I have a planned route for a specific lane which is safe for me to access?
        old_preceding, old_following = self.road.neighbour_vehicles(self)
        self_pred_a = self.acceleration(ego_vehicle=self, front_vehicle=new_preceding)
        if self.route and self.route[0][2]:
            # Wrong direction
            if np.sign(lane_index[2] - self.target_lane_index[2]) != np.sign(self.route[0][2] - self.target_lane_index[2]):
                return False
            # Unsafe braking required
            elif self_pred_a < -self.LANE_CHANGE_MAX_BRAKING_IMPOSED:
                return False

So maybe having a planned route with a lane_id set to 2 instead of None is enough, I will try it.

[eleurent]

https://user-images.githubusercontent.com/1706935/148241437-0721414c-3213-43df-9ecf-d3ae4922a7dd.mp4

This is what I get on my exit_env environment, after adding the following lines in create_vehicles().

            vehicle = vehicles_type.create_random(self.road,
                                                  lane_from="0",
                                                  lane_to="1",
                                                  lane_id=lane_id,
                                                  speed=lane.speed_limit,
                                                  spacing=1 / self.config["vehicles_density"],
                                                  ).plan_route_to("exit")
            graph = self.road.network.graph
            vehicle.route = [(li[0], li[1], len(graph[li[0]][li[1]])-1)
                             if li[1] in ['1', '2'] else li for li in vehicle.route]
            vehicle.enable_lane_change = True

This sets the destination of every vehicle as exit, and their target lane (for the (0,1) and (1,2) segments) to L-1, where L is the number of lanes.

However, if a vehicle does not reach the correct lane in time (because others are in the way), they will still try to change to track the exit lane at the end of road segment (1, 2), which will typically cause a collision. Maybe another mechanism can be added to prevent that (in follow_road, don't select the next planned segment if it is too far). Or maybe this is too hacky, and this should all be included inside the planning procedure. But having lane planning + Mobil seems a bit contradictory, and would require replanning if the plan cannot be executed.

[TheNeeloy]

Thank you for the detailed and clear explanation of how the graph is set up and how routes work!

I added this code after I generate a non-ego vehicle in my environment to set its route's preferred lane to be at the very right:

curr_vehicle.plan_route_to("e")    # "e" is the name of the node at the end of the highway
graph = self.road.network.graph
curr_vehicle.route = [(li[0], li[1], len(graph[li[0]][li[1]])-1) for li in curr_vehicle.route]

And it does the expected behavior for the blue and black cars below when the highway density is low:

https://user-images.githubusercontent.com/14181513/148443593-c672a15c-6f01-412a-9bb0-bdb8d1542485.mp4

In the above environment, the green car is the ego vehicle is green, aggressive cars are black, defensive cars are blue, and a crashed vehicle I spawned is in red. I am forcing non-ego cars to merge to the right lane before they reach the crashed vehicle.

When I increase the density of non-ego vehicles on the highway and similarly force their preferred lane to be on the right side, it seems like cars merging right will sometimes side-swipe cars that are next to it or slightly behind it on the right lane while merging in, or brake check cars behind it after merging in, or rear end cars as they merge in.

https://user-images.githubusercontent.com/14181513/148444330-5dfca56a-89ca-4691-9974-f6855ad86d5c.mp4

Are there suggested parameters I should change of the non-ego vehicles to minimize the probability of crashes occurring in these high density scenarios? I can also try to increase the length of the highway before the spawned crashed vehicle to give cars a longer chance to merge right, but I don't know if that will fix the side-swipe or brake check issues. When deciding when to switch lanes, do IDMVehicles consider the distance of cars behind it in the desired lane?

Thanks for your time!

[eleurent]

Hi! The lane change decision is carried out by the MOBIL model, which theoretically has a mechanism to avoid this kind of scenarios: when considering a lane change, a vehicle computes its position after the lane change, finds its new following vehicle on that lane, and checks that the deceleration that was imposed on that following vehicle is lower than a threshold. This is done here: https://github.com/eleurent/highway-env/blob/9d63973da854584fe51b00ccee7b24b1bf031418/highway_env/vehicle/behavior.py#L230

This is supposed to prevent the lane changes you observe. Clearly, it is not the case, so something must be going wrong. Here are two hypotheses:

• In the original MOBIL model, the lane changes were assumed to be instantaneous. In contrast, in this project it takes some time for a vehicle to complete a lane change, and during this time the new following vehicle keeps accelerating as if nothing was on the lane. A possible fix would be to make the following vehicle consider any vehicle currently changing to its lane as already on the lane, so that it starts braking earlier. I did something similar here (but for the changing vehicle instead): https://github.com/eleurent/highway-env/blob/9d63973da854584fe51b00ccee7b24b1bf031418/highway_env/vehicle/behavior.py#L104

• another possibility is that the IDM/MOBIL parameters are too aggressive. Decreasing LANE_CHANGE_MAX_BRAKING_IMPOSED makes vehicle less likely to change lane in front of someone else (a higher safety distance is required), and increasing COMFORT_ACC_MIN makes vehicles brake faster when another car merges in front of them.

If you want to share your environment code with me, I can help you investigate and try to find an acceptable solution.

[TheNeeloy]

Hi!

Thank you so much for your advice, and I apologize for the delayed response in getting back to you about this. Currently, my environment spans a length of 330 meters, and I can spawn 7 non-ego vehicles into the scenario evenly across the highway without causing crashes during an episode. As I increase to 9 or more non-ego vehicles, side-swipes, rear end, etc. crashes occur more often.

I tried decreasing LANE_CHANGE_MAX_BRAKING_IMPOSED and increasing COMFORT_ACC_MIN and ACC_MAX with higher density scenarios to no avail.

I was thinking about whether the MOBIL model's assumption that it can merge instantaneously is causing the crashes, but I noticed there were times when a car would merge into the other lane even when there is another car directly next to it (side by side).

I have published my environment code to this repo: https://github.com/TheNeeloy/highway-env

The environment in question is highway_env.envs.anomaly_exit_env. I added a script which you can run from the project directory to visualize the environment: python hello_highway.py

If you have the chance, I would be very much thankful if you could take a look at the parameters used or whether a different solution would be more appropriate.

Thanks for your time!

[TheNeeloy]

Sequence of 5 episodes with 7 non-ego vehicles max with no crashes:

https://user-images.githubusercontent.com/14181513/152594661-7a2c4eb8-87a1-42fd-b969-a2e3b0eae102.mp4

Sequence of 5 episodes with 10 non-ego vehicles max with crashes:

https://user-images.githubusercontent.com/14181513/152594816-d33da010-f4de-4d02-8713-9b235530cf79.mp4

[TheNeeloy]

I think the problem of crashing cars may be originating from what you said earlier about how cars will switch lanes at the end of the lane if they weren't able to do so earlier:

However, if a vehicle does not reach the correct lane in time (because others are in the way), they will still try to change to track the exit lane at the end of road segment (1, 2), which will typically cause a collision.

My 2 lane highway scenario with no exit has several intermediate nodes between the start and end of the road that mimic the construction of my exit scenario. I think I can just use a RoadNetwork.straight_road_network instead of my current construction of the 2 lane highway scenario.

[TheNeeloy]

https://user-images.githubusercontent.com/14181513/152725354-8e0bcea4-c534-4f83-a4b6-4940fd9b6c9e.mp4

By changing the graph to use fewer nodes, I stopped the crashes from occurring. Then, I also had to comment out from behavior.py the following line to ensure that stopped IDM vehicles stuck behind the red crashed vehicle were still able to merge right:

# Only change lane when the vehicle is moving
if np.abs(self.speed) < 1:
    continue

Do you think there would be a better way to solve the issue of stuck vehicles? I played around with the IDM parameters further and read https://github.com/eleurent/highway-env/issues/259#issuecomment-1015873714 and https://github.com/eleurent/highway-env/issues/81#issuecomment-640223373 until I just commented out the condition I wrote above.

[eleurent]

Hi @TheNeeloy

First, in your "Sequence of 5 episodes with 10 non-ego vehicles max with crashes:", I can see only one crash, happening at 0:05. It is very strange that the vehicle that cuts was allowed to change lane, since there is another car on that lane just a few meters behind, so this should have been stopped by the MAX_BRAKING_IMPOSED criteria. If you can consistently reproduce it (find the random seed in the episode stats), it would be good to investigate what's going on there, e.g. what was the computed imposed braking.

I think it's a shame you went back to the straight road network, I liked your exit ramp scene a lot :) But its true that currently, if a vehicle has planned in its route to take the exit and could not reach the exit lane early enough; it is just going to cross the road when it reaches the fork. This behaviour could be avoided though, I think? it suffices to check when moving to the next road segment in the planned route that it is reachable from the current position, and else to just keep following the current lane. I could submit a patch, if you're interested.

About the line you cited above, I agree that removing it would definitely help avoiding stuck vehicles. It was introduced to fix this issue which may be a bit too specific. I think your use-case is more common, and that other issue should probably be addressed in a different way.