Motion Planning for Multiple Autonomous Vehicles
There is an Indian driving where you can drive anywhere, at any speed, and make any turn anytime, as long as you do not dash into someone 'stronger' than you; where the speeds vary from manually ridden rickshaws to Ferraris and the sizes vary from bicycles to overloaded trucks, all on the same road; where the motorbikes overtake cars and the cars overtake bicycles like a criss-cross between hurdles race played simultaneously with multiple age groups; where it is more important to know when not to follow the traffic rules, than to know when to actually follow the traffic rules; where the driving is not limited to steering and speed control alone, but extends to horns and shouts; where you should not be so fast so as to assume a well-built road ahead, and not so slow so as to be called a dumb; and where glamour awareness around is more important than the traffic awareness.
And there is a British traffic where you have no other option than to follow the vehicle in front (if any); drive within the predefined lanes and within the predefined speed limits; change lane if possible; see and follow all the signs and traffic signals, be it marked on the road, marked on a signboard aside the road, marked on a signboard vertically above, or a small signboard of blockage on the road; look for all the vehicles and pedestrians at every side of the road and know the priorities associated; if you happen to make mistakes, pray for the absence of video cameras nearby; horn is an extreme indication of the fault of the person in front.
Similar to the fact that Indians believe in fitting more people in the cars and buses than allowed, more food in their stomach than possible, and more luggage in their bags than possible; the Indian traffic fits in more vehicles on the roads than the maximum possible bandwidth with a lane oriented traffic (largely possible due to the varying sizes of the vehicles). Be it the natural differences in speeds; or the factors of social prestige, stud-ness, or mere impatience; some vehicles have to overtake the others, even if remotely possible. And when you are aware that the minor accidents are well fought and immediately forgotten, the risk is worth taking. (No driving license, no points lost!). This is what makes the Indian traffic more efficient than any organized traffic with vehicles as diverse in speeds and sizes, as in the Indian traffic.
Hence, while in India expect a complete chaos, and while in Britain expect similar types of vehicles neatly following each other, where the chaos is largely triggered by diversity of vehicles hence necessitating an unorganized traffic. So all you need to cause a chaos in British traffic is to make it diverse. While riding bullock carts or flooding in motorbikes may not be a good idea - even though very slow, autonomous vehicles may be conspiring towards this direction.
In most simple card games, it is easy to teach children the rules of the game, enable them understand the game logic and the game dynamics, which makes them capable of making near-optimal moves to every situation so that in most cases the luckiest player wins. However, it is hard to teach them the cheating principles which are widespread, require skill and experience, difficult to implement, and are largely opponent-based. The winning edge mostly lies in these cheating skills more than anything else. Similarly, it is easy to learn driving as a simple vehicle following, lane change and situational assessment mechanism. In a card game, playing with skilful cheaters, you can be badly defeated and forced to quit if you simply follow the rules, you can be defeated if you are not a good cheater, you can win if you are too good in cheating, and you can be caught if you are not careful in cheating. The same rules apply for driving in unorganized traffic. While you may learn conventional driving, if you only follow those principles, you do not survive; if you are clever enough, you just survive; if you are know the tricks well, you succeed in getting the best bargain out of the other vehicles usually implying many overtakes at great speeds; and if you try too much, you end up in an accident!
While the research community is busy teaching the autonomous vehicles the general traffic rules and driving primitives, which are mainly intended for an organized traffic; my work deals with teaching the vehicles the tricks and cheats of unorganized traffic. The long term aim is to have autonomous vehicles in an unorganized traffic, or to fill the road with application specific diverse autonomous vehicles which necessitate an unorganized way of operation. Teaching autonomous vehicles to drive is similar to teaching a newbie how to drive, while it is accepted that teaching is in general a frustrating task where the teacher is always under the impression that the student is dumb and lazy, and the student has exactly the same views regarding the teacher. The good thing about teaching autonomous vehicles is that the latter is untrue; although the bad thing is that you can never challenge their level of dumbness. Humans have inbuilt intelligence, and thanks to a set of intelligent algorithms which are well established, inducing similar intelligence in machines is not so hard.
When it comes to the strategy of driving - there are goal shooters, chess masters, and boxers. Football is played more intensely off the field than on the field, with the goal shooters (or sampling based planners) usual targets of infinite love and criticism. What do they actually consider in seconds of ball control? Certainly, mostly the most straightforward choices, although some thought process may be devoted to select the side and approximate position of shoot by considering random choices. In driving, after basic steering and speed control (or the control problem), this corresponds to driving as straight as possible, overcoming slowest of vehicles as they come around, and avoiding anyone passing through (the planning problem). In all the cases, the rather straightforward and quick looking way may be decided; for which the humans use their ability to identify and analyse obstacles around, deliberate their actions in the future, and quickly mine out safe distances to be maintained and hence the steering required; while machines can use algorithms like Genetic Algorithms, Rapidly-exploring Random Trees, etc. While driving it is very important to decide whether to overtake a vehicle ahead, or instead follow it (the coordination problem). This affects the driving speed and avoidance strategy. Humans learn to identify feasibility of an overtaking manuever, and especially in the initial phases usually get wrong which is the cause of collisions and quarrels; while machines can deliberate into the future using competing plans and sensed speeds. Communication, if available, enables to know the participating vehicle's intentions for better feasibility assessment. This option is only possible with an autonomous-vehicle only scenario, a valid possibility much into the future.
Kids know a simple rule - if you are smart, prove your smartness in the smartest game of all times. The chess masters (or graph based planners) are ultimate genius who think over all the combination of moves right into the future, know which moves are clearly good and bad for consideration, and formulate the best strategy. In a road, this corresponds to exploiting the road architecture to make the overall planning time effective, while strategically deciding all the combinations of overtakes, vehicle following behaviours, vehicle avoidance strategies, etc. Again, communication enables to make sure that two vehicles follow exactly the same overall strategy. Never even think to mess around with the boxers (or reactive planners) who have unbelievable reflexes, and can rip you apart in seconds, or defend themselves most strongly in the blink of an eye. In a road, this corresponds to assessing the immediate scenario to take the basic decision of where to turn, by what magnitude, and at what speed. One may use algorithms like Fuzzy Logic, Potential Fields and Elastic Strip; or may frame rules similar to what you would give to a kid explaining him/her how to act in every different situation. Small deliberative means may be helpful in better decision making regarding overtake feasibility, side of overtake and obstacle avoidance, etc. The tradeoff is always between deliberation, offering near-optimal and near-complete solutions at the expense of computational time (which significantly increases with an increase in the number of vehicles); and reactiveness offering faintly optimal and faintly complete solutions for odd-looking scenarios, while being very computationally efficient for any number of vehicles.
Related Publications
- R. Kala (2016) On-Road Intelligent Vehicles: Motion Planning for Intelligent Transportation Systems, Elsevier, Waltham, MA.
- R. Kala (2013) Motion Planning for Multiple Autonomous Vehicles (14 videos/13 hours Video Lecture Series), School of Cybernetics, School of Systems Engineering, University of Reading, UK. Available at: http://rkala.in/autonomousvehiclesvideos.php
- R. Kala, K. Warwick (2014) Dynamic Distributed Lanes: Motion Planning for Multiple Autonomous Vehicles. Applied Intelligence, 41(1): 260-281. (Download Paper)
- R. Kala, K. Warwick (2014) Heuristic based evolution for the coordination of autonomous vehicles in the absence of speed lanes. Applied Soft Computing, 19: 387–402 (Download Paper)
- R. Kala, K. Warwick (2013) Planning Autonomous Vehicles in the Absence of Speed Lanes using an Elastic Strip. IEEE Transactions on Intelligent Transportation Systems, 14(4): 1743-1752. (Download Paper)
- R. Kala, K. Warwick (2013) Multi-Level Planning for Semi-Autonomous Vehicles in Traffic Scenarios based on Separation Maximization. Journal of Intelligent and Robotic Systems, 72(3-4): 559-590. (Download Paper)
- R. Kala, K. Warwick (2013) Motion Planning of Autonomous Vehicles in a Non-Autonomous Vehicle Environment without Speed Lanes. Engineering Applications of Artificial Intelligence, 26(5-6): 1588–1601. (Download Paper)
- R. Kala, K. Warwick (2015) Reactive Planning of Autonomous Vehicles for Traffic Scenarios, Electronics, 4(4), 739-762. (Download Paper) (Download PPT)
- R. Kala, K. Warwick (2015) Motion Planning of Autonomous Vehicles on a Dual Carriageway without Speed Lanes. Electronics, 4(1): 59-81. (Download Paper) (Download PPT)
- C. J. Shackleton, R. Kala, K. Warwick (2013) Sensor-Based Trajectory Generation for Advanced Driver Assistance System. Robotics, 2(1): 19-35. (Download Paper)
- R. Kala, K. Warwick (2011) Multi-Vehicle Planning using RRT-Connect. Paladyn Journal of Behavioural Robotics, 2(3): 134-144. (Download Paper)
- R. Kala, K. Warwick (2012) Planning autonomous vehicles in the absence of speed lanes using lateral potentials. In Proceedings of the 2012 IEEE Intelligent Vehicles Symposium, Alcalá de Henares, Spain, pp. 597-602. (Download Paper) (Download PPT) (View Video)
- R. Kala, K. Warwick (2011) Planning of Multiple Autonomous Vehicles using RRT. In Proceedings of the 10th IEEE International Conference on Cybernetic Intelligent Systems, Docklands, London, pp. 20-25. (Download Paper) (Download PPT)
