In my earlier article on robocar challenges I gave very brief coverage to the issue of parking. Challenged on that, I thought it was time to expand.

The world "parking" means many things, and the many classes of parking problems have varying difficulties.

The taxi doesn't park

One of the simplest solutions to parking involves robotaxi service. Such vehicles don't really park, at least not where they dropped you off. They drop you off and go to their next customer. If they don't have another ride, they can deliberately go to a place where they know they can easily park to wait. They don't need to tackle a parking space that's challenging at all.

Simple non-crowded lots

Parking in basic parking lots -- typical open ground lots that are not close to full -- is a pretty easy problem. So easy in fact, that we've seen a number of demonstrations, ranging back to Junior 3 and Audi Piloted Parking. Cars in the showroom now will identify parking spots for you (and tell you if you fit.) They have done basic parallel parking (with you on the brakes) for several years, and are starting to now even do it with you out of the car (but watching from a distance.) At CES VW showed the special case of parking in your own garage or driveway, where you show the car where it's going to go.

The early demos required empty parking lots with no pedestrians, and even no other moving cars, but today reasonably well-behaved other cars should not be a big problem. That's the thing about non-crowded lots: People are not hunting or competing for spaces. The robocars actually would be very happy to seek out the large empty sections at the back of most parking lots because you aren't going to be walking out that far, the car is going to come get you.

The biggest issue is the question of pedestrians who can appear out from behind a minivan. The answer to this is simply that vehicles that are parking can and do go slow, and slow automatically gives you a big safety boost. At parking lot speed, you really can stop very quickly if a pedestrian appears out of nowhere. The car, after all, is not in a hurry, and can slow itself when close to minivans, or if it has noticed pedestrians who are moving near it and have disappeared behind vehicles. Out at the back of a parking lot, nobody cares if you go 5 km/h, or even right down the center of the lane to assure there are no surprises.

To the right we see a picture of Junior 3 entering a parking lot, hunting for a space and taking it -- in 2009.

Mapping

Mapping is still desirable for parking lots. This is particularly true because parking lots, not being public roads, set up their own sets of rules and put up signs meant only for humans. They may direct traffic to be one-way in certain areas in nonstandard ways. They may have gates when you have to pay or insert tickets. Parking spots will be marked reserved for certain cars (Electric vehicle, expectant mother, wheelchair, employee of the month, CEO, customers of company X) with signs meant for humans.

It's not necessarily super hard to map a parking lot, just time consuming to encode all these rules. Unlike roads, which everybody drives, any given parking lot likely only serves the people who live, work or shop next to it -- you will never park in 95% of the lots in your city, though you will drive most of its main roads. Somebody has to pay for the cost of that mapping -- either because lots of people want to use the lot, or because the owner of the lot wants to encourage robocars. Fortunately, with the robocars doing things like using the least popular spots, or even valet parking as described below, there is a strong incentive to the owner of a lot to get it mapped and keep it mapped. Only lots that never fill out would have no incentive, and those lots can often be parked in without a map.

While you want trained mappers to confirm the geometry of a parking lot, coding in the signs and special rules is a task easily left to the parking lot owner. If the lot manager forgets to tag the CEO's space as reserved, nobody is hurt (except the lot manager when the CEO arrives.)

Robocar parking mistakes are easy to fix. Robocars can put a phone number or URL on the back where you can go to complain about a robocar that is parked badly or blocking things. As long as that doesn't happen too often, the cost of the support desk is manageable. The folks at the support desk can look out with the robot's sensors and tell it to move. It's not like finding a human driven car blocking something, where you have to find the owner. In a minute, the robocar will be gone.

More crowded lots

The challenge of parking lots, in spite of the low speeds, is that they don't have well defined rules of the road. People ignore the arrows on the ground. They pause and wait for cars to exit. In really crowded lots, cars follow people who are leaving at walking speed, hoping to get dibs on their spot. They wait, blocking traffic, for a spot they claim as theirs. People fight for spots and steal spots. People park badly and cross over the lines.

As far as I know, nobody has tried to solve this challenge, and so it remains unsolved. It is one of the few problems in robocars that actually deserves the label of "AI," though some think all driving is AI.

Even so, on the grand scheme of things, my intuition is that this is not one of the grand unsolved challenges of AI. Parking lots don't have legalized rules of the road, but they do have rules and principles, and we all learn them the more we park. Creating a system that can do well with these rules using various AI tools seems like a doable challenge when the time comes. My intuition is that it's a lot easier than winning on Jeopardy. This system will be able to take advantage of a couple of special abilities of the robocars:

• They will be able to park and exit spots quickly and efficiently. They won't be like the people you always see who do a 5 point turn to exit their parking spot when you (but not they) can see they still have 5 feet of room behind them.
• In general, they will be superb parkers, centering themselves as well as possible inside spots
• They don't need room to open their doors, so they can park right next to walls and pillars.
• Yes, they could also park right next to badly parked cars which have encroached into other spaces and thus made a space no human can use. There is a risk of course that the bad parker, who finds they can't get in one side, might retaliate. (I've had a guy rip my mirror off in revenge.) In this case, though, they will have a photo of the licence plate and a sensor record of the revenge taking place!
• In the event of problems or deadlock, they are open to the idea of just giving up and parking somewhere farther away that is easier to park in. Unlike humans they could drive as quickly in reverse as forward to back out of situations.

In spite of all this, the cars will want to avoid the full parking lots where the chaos happens. If there is another lot not far away, they will just go there, and require a couple minutes more advance notice from their master when summoned to pick them up. If there is nowhere nearby to park, the car will tell its passenger that she has to do the parking.

Robo-valet zones

Even in the most crowded lots, there is the potential to easily create zones of the parking lot that are marked:

"Robot Valet Parking only. All other cars may be blocked in or towed. No pedestrians."

In the car's map, it will indicate what server is handling the robo-valet section, though it is possible to have it work without any communication at all.

In the most basic version the car would ask permission to enter the lot. The database might even assign it a spot, but generally it would just enter and take any spot. By "any spot", I mean any piece of pavement, ignoring the lines on the ground. At first the cars would choose spots that let them have an unblocked pack to leave. As soon as too many cars arrive to do that, they would switch to a more dense, valet pattern that blocks in some cars (the ones who said they were leaving latest.) It would report where it parked to the database, as well as how to send it a message, and when it expects to leave.

Other cars would arrive. Eventually one would block in your car. If the database has given them a way to communicate (probably over the internet, though if they had V2V they could use that) they might discuss who plans to leave first, and the cars would adjust themselves to put the cars that will leave sooner at the front. This is strongly in the interests of the cars. If you plan to be there a while, you want to go to the back so you don't have to keep moving to let cars behind you out. But it still works, just not as well, if the cars just take any available spot.

When it's time to leave, the cars could try to send a message over the data networks to the cars in front of them, but a simpler approach might be to just nudge slightly forward -- a few cm will do it. This will cause the car in the direction of the nudge to notice, and it too would nudge forward, and so on, and so on until the front car moves out, and then all the cars in that row can move out, including your car, which leaves the lot. Then the other cars can move in to fill the spot. If they have a database which maps the cars in that section, they could try to be clever in how they re-fill the empty column to minimize movement.

There are even faster algorithms if you leave a few empty spaces. Robocars have the ability to move in concert to "move the space" and put it next to a car that wants to exit. It's more efficient, but not needed.

The database becomes more useful if a human driver ignores the signs and tries to park in the lot. That's because the database is the simplest way of spotting a vehicle that's not supposed to be there. As a first step, the cars in the lot could start flashing their lights and honking their horns at the interloper, or even speak human language messages out a speaker. "Hey, this is the robot valet lot, you are blocking me in! We're calling a tow truck to come remove you if you don't leave." Some idiots may still try, and the robots could arrange so that almost all of them can still get out, and if not, they might call that tow truck.

The robo-valet section can be at the back of the parking lot, or the top of a structure -- those places the humans park in last. The owner of the lot has a huge incentive to do this, since they can make much more efficient use of their land with the tight valet-dense parking. All the owner has to do is register the lot section in a database -- a database that a company like Google would probably be happy to offer for free to benefit their cars.

Human valets could also park cars in this area. They would just need to use an app on their smartphone that tells them where to park and allows them to register that they did it. The robots will want the human-parked cars to park at the back, because they will move out of the way when it's time for the human parked car to be driven back out.

The main requirements for this parking area would be that it be reachable from the outside without going through a zone of chaos, and that it then be possible to also reach the pickup/dropoff point for passengers without the risk of getting stuck in chaos. Larger lots tend to have entrance lanes without spots on them that serve this purpose.

Pedestrians will still enter the lot, in spite of the sign. Just go extra slow if they are there, and perhaps talk to them and ask them to leave. While you won't actually present a danger to them at your low speed, they probably will heed the advice of 3000lb robots. Perhaps tell them they have 15 seconds to put down their weapon.

Robotic sign?

To get really clever, the sign marking the border of the Robo-Valet area might itself be on a small robot. Thus, when the robo-valet area gets full, the sign can move to expand the area if space is available. You could expand even into areas occupied by human-parked cars -- just know that they are there and don't block them in -- or move out of their way when needed. Eventually they leave and only robocars enter.

When the demand goes down, the sign can easily move to shrink the valet area.