Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2002-2025 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file MSLaneChanger.h
15 : /// @author Christian Roessel
16 : /// @author Daniel Krajzewicz
17 : /// @author Michael Behrisch
18 : /// @author Jakob Erdmann
19 : /// @date Fri, 01 Feb 2002
20 : ///
21 : // Performs lane changing of vehicles
22 : /****************************************************************************/
23 : #pragma once
24 : #include <config.h>
25 :
26 : #include "MSLane.h"
27 : #include "MSEdge.h"
28 : #include "MSVehicle.h"
29 : #include <vector>
30 : #include <utils/iodevices/OutputDevice.h>
31 :
32 :
33 : // ===========================================================================
34 : // class declarations
35 : // ===========================================================================
36 :
37 :
38 : // ===========================================================================
39 : // class definitions
40 : // ===========================================================================
41 : /**
42 : * @class MSLaneChanger
43 : * @brief Performs lane changing of vehicles
44 : */
45 : class MSLaneChanger {
46 : public:
47 : /// Constructor
48 : MSLaneChanger(const std::vector<MSLane*>* lanes, bool allowChanging);
49 :
50 : /// Destructor.
51 : virtual ~MSLaneChanger();
52 :
53 : /// Start lane-change-process for all vehicles on the edge'e lanes.
54 : void laneChange(SUMOTime t);
55 :
56 : public:
57 : /** Structure used for lane-change. For every lane you have to
58 : know four vehicles, the change-candidate veh and its follower
59 : and leader. Further, information about the last vehicle that changed
60 : into this lane is needed */
61 : struct ChangeElem {
62 :
63 : ChangeElem(MSLane* _lane);
64 :
65 : /// @brief Register that vehicle belongs to Changer Item to after LC decisions
66 : void registerHop(MSVehicle* vehicle);
67 :
68 : ///@brief the leader vehicle for the current change candidate
69 : MSVehicle* lead;
70 : ///@brief the lane corresponding to this ChangeElem (the current change candidate is on this lane)
71 : MSLane* lane;
72 : ///@brief last vehicle that changed into this lane
73 : MSVehicle* hoppedVeh;
74 : /// @brief the next vehicle downstream of the ego vehicle that is blocked from changing to this lane
75 : MSVehicle* lastBlocked;
76 : /// @brief the farthest downstream vehicle on this edge that is blocked from changing to this lane
77 : MSVehicle* firstBlocked;
78 : /// @brief the next vehicle downstream of the ego vehicle that is stopped (and thus an obstacle)
79 : MSVehicle* lastStopped;
80 :
81 : double dens;
82 :
83 : /// @brief whether changing is possible to either direction
84 : bool mayChangeRight;
85 : bool mayChangeLeft;
86 :
87 : /// relative indices of internal lanes with the same origin lane (siblings)
88 : /// only used for changes on internal edges
89 : std::vector<int> siblings;
90 :
91 : /// @name Members which are used only by MSLaneChangerSublane
92 : /// @{
93 : // the vehicles in front of the current vehicle (only on the current edge, continously updated during change() )
94 : MSLeaderInfo ahead;
95 :
96 : // the vehicles in front of the current vehicle (including those on the next edge, contiously update during change() ))
97 : MSLeaderDistanceInfo aheadNext;
98 :
99 : /// vehicles that cannot be stored in ahead because they are outside the lane bounds
100 : std::vector<MSVehicle*> outsideBounds;
101 :
102 : /// visibility distance to the closest zipper link that may be encountered when driving on this lane
103 : double zipperDist;
104 :
105 : /// the back position of the last blocked vehicle that wants to change to this lane
106 : double lastBlockedBackPos;
107 :
108 : /// the waiting time of the last blocked vehicle that wants to change to this lane
109 : SUMOTime lastBlockedWaitingTime;
110 : ///@}
111 :
112 : };
113 :
114 : public:
115 : /** @brief The list of changers;
116 : For each lane, a ChangeElem is being build */
117 : typedef std::vector< ChangeElem > Changer;
118 :
119 : /// the iterator moving over the ChangeElems
120 : typedef Changer::iterator ChangerIt;
121 :
122 : /// the iterator moving over the ChangeElems
123 : typedef Changer::const_iterator ConstChangerIt;
124 :
125 : /// @brief return changer (only to be used by MSLaneChangerSublane from another instance)
126 : Changer& getChanger() {
127 : return myChanger;
128 : }
129 :
130 : /// @brief retrieve properties of a blocked vehicle that wants to chane to the lane with the given index
131 : std::pair<double, SUMOTime> getLastBlocked(int index) const;
132 :
133 : protected:
134 : /// Initialize the changer before looping over all vehicles.
135 : virtual void initChanger();
136 :
137 : /** @brief Check if there is a single change-candidate in the changer.
138 : Returns true if there is one. */
139 : bool vehInChanger() const {
140 : // If there is at least one valid vehicle under the veh's in myChanger
141 : // return true.
142 521710561 : for (ConstChangerIt ce = myChanger.begin(); ce != myChanger.end(); ++ce) {
143 354148824 : if (veh(ce) != 0) {
144 : return true;
145 : }
146 : }
147 : return false;
148 : }
149 :
150 : /** Returns the furthes unhandled vehicle on this change-elements lane
151 : or 0 if there is none. */
152 : MSVehicle* veh(ConstChangerIt ce) const {
153 : // If ce has a valid vehicle, return it. Otherwise return 0.
154 5571993638 : if (!ce->lane->myVehicles.empty()) {
155 5319272462 : return ce->lane->myVehicles.back();
156 : } else {
157 : return 0;
158 : }
159 : }
160 :
161 :
162 : /** Find a new candidate and try to change it. */
163 : virtual bool change();
164 :
165 :
166 : /** try changing to the opposite direction edge. */
167 : bool changeOpposite(MSVehicle* vehicle, std::pair<MSVehicle*, double> leader, MSVehicle* lastStopped);
168 :
169 : std::pair<MSVehicle* const, double> getOncomingVehicle(const MSLane* opposite, std::pair<MSVehicle*,
170 : double> neighOncoming, double searchDist, double& vMax, const MSVehicle* overtaken = nullptr,
171 : MSLane::MinorLinkMode mLinkMode = MSLane::MinorLinkMode::FOLLOW_NEVER);
172 :
173 : std::pair<MSVehicle* const, double> getOncomingOppositeVehicle(const MSVehicle* vehicle,
174 : std::pair<MSVehicle*, double> overtaken, double searchDist);
175 :
176 : /** Update changer for vehicles that did not change */
177 : void registerUnchanged(MSVehicle* vehicle);
178 :
179 : /// @brief Take into account traci LC-commands.
180 : /// @note This is currently only used within non-actionsteps.
181 : void checkTraCICommands(MSVehicle* vehicle);
182 :
183 : /// @brief Execute TraCI LC-commands.
184 : /// @note This is currently only used within non-actionsteps for the non-sublane model.
185 : /// @return whether lane was changed
186 : bool applyTraCICommands(MSVehicle* vehicle);
187 :
188 : /** After the possible change, update the changer. */
189 : virtual void updateChanger(bool vehHasChanged);
190 :
191 : /** During lane-change a temporary vehicle container is filled within
192 : the lanes (bad practice to modify foreign members, I know). Swap
193 : this container with the real one. */
194 : void updateLanes(SUMOTime t);
195 :
196 : /** @brief Find current candidate.
197 : If there is none, myChanger.end() is returned. */
198 : ChangerIt findCandidate();
199 :
200 : /* @brief check whether lane changing in the given direction is desirable
201 : * and possible */
202 : int checkChangeWithinEdge(
203 : int laneOffset,
204 : const std::pair<MSVehicle* const, double>& leader,
205 : const std::vector<MSVehicle::LaneQ>& preb) const;
206 :
207 : /* @brief check whether lane changing in the given direction is desirable
208 : * and possible */
209 : int checkChange(
210 : int laneOffset,
211 : const MSLane* targetLane,
212 : const std::pair<MSVehicle* const, double>& leader,
213 : const std::pair<MSVehicle* const, double>& follower,
214 : const std::pair<MSVehicle* const, double>& neighLead,
215 : const std::pair<MSVehicle* const, double>& neighFollow,
216 : const std::vector<MSVehicle::LaneQ>& preb) const;
217 :
218 : /* @brief call lanechange model to check the merits of an opposite-direction
219 : * change and update state accordingly */
220 : virtual bool checkChangeOpposite(
221 : MSVehicle* vehicle,
222 : int laneOffset,
223 : MSLane* targetLane,
224 : const std::pair<MSVehicle* const, double>& leader,
225 : const std::pair<MSVehicle* const, double>& neighLead,
226 : const std::pair<MSVehicle* const, double>& neighFollow,
227 : const std::vector<MSVehicle::LaneQ>& preb);
228 :
229 :
230 : /* @brief start the lane change maneuver (and finish it instantly if gLaneChangeDuration == 0)
231 : * @return False when aborting the change due to being remote controlled*/
232 : bool startChange(MSVehicle* vehicle, ChangerIt& from, int direction);
233 :
234 : /// @brief continue a lane change maneuver and return whether the vehicle has completely moved onto the new lane (used if gLaneChangeDuration > 0)
235 : bool continueChange(MSVehicle* vehicle, ChangerIt& from);
236 :
237 : std::pair<MSVehicle* const, double> getRealFollower(const ChangerIt& target) const;
238 :
239 : std::pair<MSVehicle* const, double> getRealLeader(const ChangerIt& target) const;
240 :
241 : /// @brief whether changing to the lane in the given direction should be considered
242 : bool mayChange(int direction) const;
243 :
244 : /// @brief return the closer follower of ego
245 : static MSVehicle* getCloserFollower(const double maxPos, MSVehicle* follow1, MSVehicle* follow2);
246 :
247 : /** @brief Compute the time and space required for overtaking the given leader
248 : * @param[in] vehicle The vehicle that wants to overtake
249 : * @param[in] leader The vehicle to be overtaken
250 : * @param[in] gap The gap between vehicle and leader
251 : * @param[out] timeToOvertake The time for overtaking
252 : * @param[out] spaceToOvertake The space for overtaking
253 : */
254 : static void computeOvertakingTime(const MSVehicle* vehicle, double vMax, const MSVehicle* leader, double gap, double& timeToOvertake, double& spaceToOvertake);
255 :
256 : /** @brief return leader vehicle that is to be overtaken
257 : * @param[out] maxSpace The maxium space that can be used for the overtaking maneuver (limits speed)
258 : * @param[in] vehicle The vehicle that wants to overtake
259 : * @param[in] leader The vehicle to be overtaken and the gap to this vehicle
260 : * @param[in] maxLookAhead The maximum lookahead distance
261 : *
262 : * This methods calls itself recursively to find the leader of a column of
263 : * vehicles to be overtaken (if there is no sufficient gap for stopping in between)
264 : */
265 : static std::pair<MSVehicle*, double> getColumnleader(double& maxSpace, MSVehicle* vehicle, std::pair<MSVehicle*, double> leader, double maxLookAhead = std::numeric_limits<double>::max());
266 :
267 : /// @brief return the next lane in conts beyond lane or nullptr
268 : static const MSLane* getLaneAfter(const MSLane* lane, const std::vector<MSLane*>& conts, bool allowMinor, bool& contsEnd);
269 :
270 : /// @brief whether vehicle has an opposite-direction stop within relevant range
271 : static bool hasOppositeStop(MSVehicle* vehicle);
272 :
273 : /// @brief decide whether to change (back or forth) for an opposite stop
274 : bool checkOppositeStop(MSVehicle* vehicle, const MSLane* oncomingLane, const MSLane* opposite, std::pair<MSVehicle*, double> leader);
275 :
276 : /** @brief avoid opposite-diretion deadlock when vehicles are stopped on both sides of the road
277 : * The method may call saveBlockerLength to affect vehicle speed in the next step
278 : */
279 : bool avoidDeadlock(MSVehicle* vehicle,
280 : std::pair<MSVehicle*, double> neighLead,
281 : std::pair<MSVehicle*, double> overtaken,
282 : std::pair<MSVehicle*, double> leader);
283 :
284 : /** @brief keep stopping to resolve opposite-diretion deadlock while there is oncoming traffic
285 : * The method may call saveBlockerLength to affect vehicle speed in the next step
286 : */
287 : bool resolveDeadlock(MSVehicle* vehicle,
288 : std::pair<MSVehicle* const, double> leader,
289 : std::pair<MSVehicle*, double> neighLead,
290 : std::pair<MSVehicle*, double> overtaken);
291 :
292 : /// @brief check whether to keep stopping for oncoming vehicles in the deadlock zone
293 : bool yieldToDeadlockOncoming(const MSVehicle* vehicle, const MSVehicle* stoppedNeigh, double dist);
294 :
295 : /// @brief check whether to yield for oncoming vehicles that have waited longer for opposite overtaking
296 : bool yieldToOppositeWaiting(const MSVehicle* vehicle, const MSVehicle* stoppedNeigh, double dist, SUMOTime deltaWait = 0);
297 :
298 : /// @brief determine for how long the vehicle can drive safely on the opposite side
299 : double computeSafeOppositeLength(MSVehicle* vehicle, double oppositeLength, const MSLane* source, double usableDist,
300 : std::pair<MSVehicle*, double> oncoming, double vMax, double oncomingSpeed,
301 : std::pair<MSVehicle*, double> neighLead,
302 : std::pair<MSVehicle*, double> overtaken,
303 : std::pair<MSVehicle*, double> neighFollow,
304 : double surplusGap, const MSLane* opposite,
305 : bool canOvertake);
306 :
307 : // @brief compute distance that can safely be driven on the opposite side
308 : static double computeSurplusGap(const MSVehicle* vehicle, const MSLane* opposite, std::pair<MSVehicle*, double> oncoming, double timeToOvertake,
309 : double spaceToOvertake, double& oncomingSpeed, bool oncomingOpposite = false);
310 :
311 : // @brief find hilltop within searchDistance
312 : static bool foundHilltop(MSVehicle* vehicle, bool foundHill, double searchDist, const std::vector<MSLane*>& bestLanes, int view, double pos, double lastMax, double hilltopThreshold);
313 :
314 : /// @brief add LaneQ for opposite lanes
315 : static std::vector<MSVehicle::LaneQ> getBestLanesOpposite(MSVehicle* vehicle, const MSLane* stopLane, double oppositeLength);
316 :
317 : /// @brief compute maximum maneuver speed
318 : static double getMaxOvertakingSpeed(const MSVehicle* vehicle, double maxSpaceToOvertake);
319 :
320 : protected:
321 : /// Container for ChangeElemements, one for every lane in the edge.
322 : Changer myChanger;
323 :
324 : /** Change-candidate. Last of the vehicles in changer. Only this one
325 : will try to change. Every vehicle on the edge will be a candidate
326 : once in the change-process. */
327 : ChangerIt myCandi;
328 :
329 : /* @brief Whether vehicles may start to change lanes on this edge
330 : * (finishing a change in progress is always permitted) */
331 : const bool myAllowsChanging;
332 :
333 : /// @brief whether this edge allows changing to the opposite direction edge
334 : const bool myChangeToOpposite;
335 :
336 : private:
337 : /// Default constructor.
338 : MSLaneChanger();
339 :
340 : /// Copy constructor.
341 : MSLaneChanger(const MSLaneChanger&);
342 :
343 : /// Assignment operator.
344 : MSLaneChanger& operator=(const MSLaneChanger&);
345 : };
|
