Autonomous Cars

Imagine a car that drives itself, and takes us to wherever we want to be. This is not a far-fetching idea now. In DARPA Urban Challenge of November 2007, six autonomous cars finished the course of city street driving. In addition, they performed stop-sign recognizing,  yielding to other cars at intersection and safe passing on the road. What an amazing achievement! Just compare this to 3 years earlier, in the 2004 DARPA Grand Challenge (the first of this kind), no car was able to reach the finishing line.

An autonomous vehicle needs 3 basic capabilities: Sensors that perceives the environment such as lane, curbs, and stop signs; a route plan that tells it where it is heading; A response strategy so that it knows when to move, when to yield to other cars and when to pass.

1. Sensing the environment

Today’s Autonomous cars are mostly equipped with laser range finders.  These laser finders (lidar) can detect objects as far as 120 meters. Such long-distance range is especially useful when the car moves in high speed. In addition, a laser rangefinder spins at 15 cycles per second, constantly gathering new data. Thus it can accurately detect changes in the environment such as another moving car.  

As the lasers rotate and scan the environment with 360-degree (horizontal) range, the data are fed into the car’s control center to form a picture of the environment. Thus laser has replaced cameras as more reliable environment senors. Some autonomous cars still have cameras, mainly for lane detection.  In addition, radars are used for close-range object dectection. Finally, every car needs GPS antennas to pinpoint its own location. In this aspect, an automous car may be smarter than a human driver for knowing its exact location.

2. Planning the route

The goal of driving is reaching a destination. A human driver needs a map to get from location A to location B. A car also needs such a map internally. This is the route plan for a car. Every autonomous car must have detailed route information for where it goes. In DARPA challenge, each car is given a Road Network Description File (RNDF), which is basically a digital street map of the environment. The RNDF contained geometric information on lanes, lane markings, stop signs, and parking lots.

3. Driving strategy
When should the car stop? When should it keep driving? These simple yet most profound choices for autonomous cars have to be defined in a coherent strategy. A simple reactive framework does not work because the situation can be complicated. At a 4-way stop intersection, the car has to understand who came first and who has the right-of-way. Then it decides whether to wait and for how long it waits. It also has to detect at real time how another car moves. On a two-lane highway, our autonomous car is behind a slow-moving car. It has to decide when to pass and with what speed it can safely pass. All these are the strategies or intelligence of an autonomous vehicle.

The top 2 winning cars,  from CMU and Stanford respectively, have demonstrated remarkable capabilites of incorporting the above 3 capabilities. They finished the 96 kilometer urban course (with stops signs and driving vehicles) within four and a half hours. This is a milestone for autonoumous driving.

The future challenges of autonomous driving include: recogniztion of pestrian crossing and make emergence stop; recognition of small objects one the ground such as cats and dogs; recognition of traffic signs such as “Right only”, “Yield” etc. It is very likely we will see fully autonomous car on city streets in 10 years.

References

Michael Montemerlo et al. and Sebastian Thrun. Junior: The Stanford Entry in the Urban Challenge Journal of Field Robotics, Special Issue on DARPA Urban Challenge, September 2008

Spoken Dialog Systems

What can be more exciting than a computer that speaks to you and understands you? We are closer to this goal than 10 years ago when the first commercial spoken dialog system launched. Since then we have seen remarkable progress in accuracy improvement on speech recognition, and flexibility of a dialog system to handle user interruption.

Today, spoken dialog systems are used in call centers to help user make reservation, in city bus hot line to give schedules, and in directory assistance. It is also used by hospitals for outreaching calls for medication reminder, and by marketing firm for survey data collection. User satisfaction with these dialog systems is mixed. AT&T’s 411 assistance has millions of calls handled automatically. I tried an automated magazine subscription service. The dialog steps are well crafted so that the machine understands most things I said (mostly “yes” or “no”). The subscription was successfully made and I was satisfied. However, many automated customer services are disappointing to the users. The sophistication of these dialog systems varies. Most of them still use a very rigid and small grammar, thus preventing flexibility when dealing with user utterance.

The ultimate and most consistent application of dialog system is on household robots. Unlike personal computer, we do not have any easy way to give command to a robot (except when they carry a keypad on their body). In addition, we want our robot to have lively interaction with us. The need for natural language communication will increase in the future, given that they do more tasks for us. Today, we already see prototypes of kitchen robots that put away dishes and clean the counter. Isn’t it nice to be able to tell the robot, “Leave that blue plate there”? Then imagine a companion robot who can help an elderly to move around the house. The lonely elderly will like to talk, and the robot can simply listen. Understanding when to listen and when to act is an important function of a robot. After all, there is conversation going on all the time in the house. We don’t want the robot to jump up at any moment.

The great era for dialog systems is still to come. We are waiting for the development for household robots. That will create need for more advanced artificial intelligence and will greatly move forward the state of art of dialog systems.

Intelligent Agents

An agent is a computer program that acts independently, mostly with a plan. For example, an online calendar system can be thought of as an agent. It is awake 24 hours a day and sends you reminder when time comes. Such a system can be smarter by linking to your future plan or projects.

A robot is an agent. It acts on its own in the physical world. It has to avoid obstacle and navigate through the physical space. A home vacuuming robot can even be programmed to wake up every day, do the cleaning, then go back to sleep. In short, an agent has a goal, and a basic plan to accomplish that goal. It is alive most of the time (including sleeping), and can wake up by itself.

By the above definition, a web server is also an agent. A web server is on 24 hours a day. It listens to incoming traffic, and identifies visitors by their IP addresses. It accepts certain visitors but rejects others (the hacker). Then the web server retrieves the document and data requested by the user. In doing so, it communicates with the back-end database server, file server, and application server. All of these are integrated together to display a seamlessly webpage to the user. Some web server also does remote communication with other web servers, such as those who deliver web services. As the user navigates the website, the web server can record and track the user’s activities. It can smartly use that informaiton to display relevant links or advertisement to the user at the right time. It can even make recommendation on certain products. All of these intelligence is built into the server. Given the large capacity of a server for handling data and software program, for knowing about other users, and for having language knowledge of text on a content page, a web server can be extremely smart. In this way, a web server has become an intelligent agent.

The only missing piece is that a web server is typically passive. It may send you a reminder or news summary, but most of the time it just waits for your visit. This may change when you need to enter daily data on a web server.  I use Kibotzer.com to track my progress in running. Every morning, I receive an email from this website to ask me to enter my new data. After I dutifully report my results back through email, the website responds by sending me (through email) a link to my updated chart. It’s interactive and feels like someone watching over me.

In the future, we will see more of such interactive servers. When a website reaches out to you everyday, it is taking initiative and it can even have its own agenda.  For example, we can build a server that tracks your projects and understands where you fall short.  It gives you gentle advice and asks you to take actions. We can have a smart financial server that trades your stock for you and gives you daily report on your gain or loss.

In addition,  a server can send you text-messages to your phone to remind your diet resolution,  and do this before your mealtime. UC San Diego has tried such a program on teenagers and have found certain success for helping the teenagers lose weight. Text-messaging is a just one form of communication. It is no different from email when you can get the email message instantly in smart phones.

The potential for intelligent agents is limitless. It can touch every area of our life, from house chore to our daily planning and to our health. My dream is help advancing the state of art in this domain. If I achieve a reasonable success in this aspect, I will be deeply happy.

The Future of Machine Intelligence

How smart can we make a machine be? Today’s robots can perform house cleaning, lawn mowing and entertaining. High-end surgery robots can operate on human heart. Agricultural robots can pick up fruits and vegetables. In the financial world, computer programs automatically decide buying and selling decision. In Internet business, intrusion is detected by computer program. Our car can now help us to stop safely with ABS, and it can drive by itself as demonstrated by this year’s DARPA contest.

Monitoring devices stay with heart patients at home, sending information to their hospital every day. Soon those devices can analyze this data, and decide when to alert the doctors.

Intelligent program is already helping Web companies to display relevant advertisement targeting to the page you are reading and or your search history. Intelligence is built in fund raising assisting program, which determines who to mail the letters to get the highest donation. Face detection is already been used in security, and soon a person’s walking pace and intention will be analyzed with the video.

The list goes on and on. There is no limit on what machines can do, and do better than humans. Eventually, will machine do everything for us and we can just lie down on the beach and become totally useless as shown in movie Wall-E? Given that people in this country gained more weight each year, and life becomes more sedate and comfortable over yeras, I can see this real possibility.

Before that day comes, we are still pushing for more intelligent machines. Machine program can replicate itself, and it never dies. Whatever knowledge it gains, it retains. This has so much advantage over humans, whose memory falters when they get older, and who cannot update their knowledge quickly or willingly. On the contrary, computer programs become smarter and more sophisticated. The task they can handle gets bigger every day. From un-manned plane to underwater explorer, from nuclear waste detector to cancer cell analyzer, machine are replacing people in more sophisticated areas. For now, it releases humans from dangerous and complex tasks, but will it eventually threaten humans in what humans can do best: composing, movie making, and scientific discovery?  When the computer can fake “creativity” with its vast memory and bag of tricks, it is not far from a real human being.

The day of intelligent machines is not far. We welcome it with both trepidation and excitement.