Home > News content

Tsinghua graduate computer professor was hijacked by gun! Recovery of American Police by "Greedy Algorithms"

via:博客园     time:2019/1/7 10:06:14     readed:1865


Source: Shi Yiyu

Editor: Zhang Qian

Never mess with a computer professor.

Recently, Shi Yiyu, an associate professor and doctoral supervisor in the Department of Computer Science, Notre Dame University, and also an associate professor in the Department of Electronics, has experienced a thrilling event.

The turning point is that Professor Shi uses Mazda Mobile Start (MMS) to successfully locate the relative position of the vehicle, and uses the most direct greedy approach (greedy algorithm) in the computer algorithm to search out the location of the vehicle. Finally, within 24 hours of being robbed, Professor Shi successfully recovered the car.

Even the police on the scene sighed:

Robbed: Two robbers with guns, take all the luggage!

According to the original plan, Professor Shi and his family drove from South Bend, Indiana, to Chicago at about 12:00 mid-time, and found that Mazda CX-9 indicated abnormal tire pressure. So Professor Shi decided to drive to a Shell gas station near Chicago after lunch to inflate tires.


At that time, there were many cars in the gas station, and some people were shopping in the shops, without any dangerous signs.

Because the gas pump at the gas station was very simple and needed four quarters to use, and did not provide tire pressure readings, Professor Shi decided to try another gas station, but after getting on, he remembered that the valve cap of the right front wheel had not been tightened and intended to get off and tighten.

Professor Shi, considering that there were pregnant women and children in the car, in order to be safe, handed the wallet to the robbers, who opened it and took out all the cash.

The robbers then returned the wallet to Professor Shi and told him to give the car keys to the robbers. Meanwhile, another robber in the car continued to urge everyone to get off.

Throw my cell phone into the pocket on the door.

After everyone got off, the robbers drove away as soon as they were smoking, and all the luggage of Professor Shi's family, including passports, green cards and so on, was still in the trunk.

Alarm: It took three times to get through 911. The police made a mistake about the model of the car.

The robbers did not steal Mrs. Shi's mobile phone, which became the only means of communication for Professor Shi's family.

After being robbed, Professor Shi first dialed 911. For the first time, he waited about ten seconds and was not connected. So the second fight, or did not succeed (so the key time 911 is not necessarily reliable) the third fight, finally through.

But the 911 operator told us that Professor Shi's license plate number Sir could not be found.

So he continued to call 911. This time, the operator was better. After Professor Shi described the case again, the operator helped to transfer to the Chicago Central Police Station. The operator of the other party asked the situation again, saying that you should call 911 directly. (This is a true emergency and you should call 911 directly.)

After waiting for about ten minutes, unlike the scene in which Professor Shi imagined a large number of police cars flocking with flashing lights, only one police car came. Two policemen got out of the car and carefully inquired about the incident, including whether they could see the appearance and age of the robbers.

Finally, when the police had finished, Professor Li Shi's car had been robbed.It took half an hour.

Then, the police found that the gas station was full of surveillance cameras, so they went into the store to watch the surveillance. But soon the policeman came out and asked another policeman, "I don't know how to upload these videos, will you?" Another policeman answered, "Neither can I. They then told Professor Shi: Never mind, detectives will come to take care of this video, and that's all we have to do!

So they decided to drive away.

But just got on the bus and came down to ask Professor Shi:

By this time Professor Shi was completely speechless:


Mazda CX-9

Then the police rushed back to the car and picked up the walkie-talkie and said:

More than forty minutes after Professor Shi's car was robbed, Professor Shi remembered a key question: He left his cell phone in the car!

The policeman suddenly looked excited: Is it an iPhone? Is there a tracking function?

Because Professor Shi and others need to use the school's email to log in to their mobile accounts, but the school's email system opens Duo-based two-step verification, so when they log in on a new mobile phone, they need to first verify by their own mobile phone or office phone, but neither way can be used. If you call school IT, think about the weekend no one, and give up.

Finally, Professor Shi's family hit Uber and went home.

Turning point: Mobile apps become the key, Professor Shi decided to find his own car.

At home in the evening, it was too late to have dinner. Professor Shi borrowed a computer from a friend and rushed back to school immediately. He used the office phone to pass two step verification and logged in to find my phone's website. Unexpectedly, although the last seed date was the same day, it was no longer possible to display the real-time location. Later, Professor Shi found that these robbers had a very clear tracking function for electronic products.

After a hard day, Professor Shi went to bed soon after he got home. The story should have come to an end, but he had a dream and woke up at five in the morning.New turning point

Professor Shi dreamed that there was a remote control on the key of the car left at home. He pressed the car and drove back by himself, and all the luggage was still on the car.

Mazda Mobile Start (MMS)

In fact, Professor Shi did not use this function much after the installation, but did not expect it to eventually become the key to recover the car.

Professor Shi immediately turned on the computer and searched it, and found that indeed MMS has an additional function, which isHelp you find a parking place。 So he immediately logged in to the app on his mobile phone, but found that the password was always incorrect. The password is reset, and the password error is still prompted. In the end, I can't. I went to the Internet to find the instructions of MMS. After careful reading, I found another possibility: there was no renewal of MMS service, so it was stopped.

So Professor Shi knows nothing except the direct distance and relative position between him and the car. (Later, it was found that the relative position would be more accurate only when it was very close to the car, and it could be wrong when it was far away.) He also took a look at the state of the engine, which is OFF, indicating that the car was parked somewhere.

Anyway, there's a clue to the car. Professor Shi called 911 immediately, and the operator said it was not urgent. You can contact the Chicago Central Police directly. We don't care.

Professor Shi called the Chicago Police again. The officer answering the phone said it was great. You have to tell the detective in charge of your case. But he's not in the office this weekend. Let me transfer you to his voice mail so that he can know it at the first time at work.

Professor Shi said patiently, "This is not a good thing to put off, is it the sooner the better?" The other side said: Okay, you give me the GPS coordinates and we'll send someone to see them.

But the car has no coordinates, it can only see the distance between the car and the user and the relative direction. Hearing this, the other side said that the police force is limited and can't help you find a car all over the street.

Finally, the other side gave a very constructive suggestion: Why don't you look for it yourself? You can call us when you find it. We must solve the rest.

The police can't depend on themselves.

Twists and turns: the road is suspected to be tracked, less than five feet from Mazda

It was six o'clock in the morning, so Professor Shi apologetically called Xiao Wang, a normally clever student, and asked him to accompany him to Chicago to find a car. Xiao Wang rushed over without saying a word. They drove into the darkness before dawn as the whole family watched anxiously.

Professor Shi handed over the driving task to Xiao Wang, and he began to collect and prepare some information on the car.

Firstly, after a brief search, it was found that according to the linear distance indicated by the MMS, the target location would probably be in the southern suburb of Chicago, an area famous for riots and shootings.

Secondly, the safe distance. The robbers had guns in their hands. According to Professor Shi's visual measurement at that time, the caliber should not exceed 9 mm. Professor Shi also checked that the effective range was about 100 meters. In this way, as long as the vehicle is always moving, it is very difficult for gunmen without professional shooting training to hit the people in the vehicle. Moreover, as long as you are always vigilant about whether anyone is approaching within 100 meters. (Note by Xin Zhiyuan: Take this case as an example, please do not follow suit.)

After checking these, Professor Shi felt a little calm.

Looking back, Professor Shi found that there was a problem with the relative position cue of the MMS, mainly because when they started, the MMS indicated that the car was in the north, while Chicago was in the west. He decided that the robbers must have left the car in Chicago, so he decided to ignore the position cue and go directly to Chicago. As a result, it is obvious that the distance of straight line decreases rapidly at high speed, which indicates that the direction is correct.

Near the I-94 130th st exit in Chicago's southern suburbs, the distance was reduced to two miles. So Professor Shi turned around the exit and found that there were parks all around, and the distance did not continue to decrease. He drove back to I-94 and went on, and the distance began to decrease. When he reached Roseland, the distance fell below a mile, but I-94 bifurcated another high-speed I-57 West here, and then only improved to I-57 and Halste at the next exit. D ST went down at high speed. At this point, the distance cue increased to 2 miles.

Finally, Professor Shi located the vehicle in the red area in the picture.


The following is an enlarged map of the region:


After getting off the highway, he quickly entered the community and once found a white car following Professor Shi. After several blocks, the car disappeared.

Professor Shi once again agreed with the students: No matter what happens, try not to park, if you must stop, you must keep the car in D gear ready to start.

Then came the most technical part of the whole story:

Because the relative orientation is unreliable, Professor Shi chose the most direct greedy approach in the computer algorithm, which is to drive in one direction until the distance is no longer significantly smaller (which means that the direction we are going is almost perpendicular to the line between us and the target), and then turn to the street in the vertical direction to continue the search.


After spending some time in a dilapidated area, the distance between 101 St St and 102 nd St of S Eberhart Ave was shown to be 200 feet, indicating that it was close to the target.


But strangely, they did not see the robbed Mazda on the roadside, and on the other streets around them, the distance was more than 200 feet. Professor Shi had no way to further reduce the distance.

Turning around, it turns out that there is actually another path between S Vernon Ave and S Eberhart Ave, which has no name and is not even shown on Google Maps, but can be seen in the above satellite map (the first road on the left side of the red mark). So they turned into the path from 101st ST ST, and the entrance was like this.


It was about a little over eight in the morning, and there was no one around. Professor Shi kept a slow pace and entered the path.

As soon as you enter the MMS, the distance indicated in the MMS begins to drop significantly again. When you drive past the penultimate garage, the garage door is closed, but the distance is less than 5 feet. The MMS gives out a reminder sound:

The car is inside!

Shooting: Grass frightens snakes. The robbers drove the car away.

They did not dare to stay much. When they transferred to 102nd ST, Professor Shi immediately dialed 911 and told the operator that the hijacked vehicle had been found. The operator asked for the location and the information of the vehicle and asked them to wait in place. The police would arrive soon.

Just as they waited nervously by the roadside, Xiao Wang reminded them to look at the distance between us and the hijacked vehicle. Professor Shi looked at it and was shocked: by this time the distance had changed to 1.5 miles, and the engine had started, indicating that the vehicle was moving!

The grass frightened the snake.

So Professor Shi, while regretting that he should park in a position where he could see the garage, immediately decided to keep up with Mazda. Unfortunately, the MMS is not designed to track vehicles in the driving state, so the updates of vehicle location and distance are not real-time.

So they drove aimlessly on the road, hoping to have a chance to see the Mazda. After more than ten minutes of searching, two policemen came. Professor Shi gave them a brief description of how to find the location of the hijacked vehicle and told them that the robbers had run away again.

The police borrowed the cell phone from Professor Shi and asked them to wait by the roadside. The police would track it down. At this time Professor Shi told the police how to use MMS positioning, and repeatedly stressed that only believe in distance, do not look at the relative position.

The policeman left his cell phone and drove off soon. But Professor Shi decided to continue to look around instead of waiting by the roadside. On the one hand, he took chances, on the other hand, he did not want to stay in one place for safety reasons.

Over the next hour, Professor Shi and the police had three phone calls: the first time, the police asked me where the tracking software was, was it Google Maps? The second time, the police said it was very close, 0.4 miles, but they did not see the car. Professor Shi told him that MMS also has a panic function, which can make the car sound a great alarm when clicked on the mobile phone; the third and last time, the police said they could not find the car and decided to return it to Professor Shi.

When the police came back to see Professor Shi, they complained about how rubbish MMS was and how hard it was to use. They asked him if he was going to continue looking for it. Professor Shi said of course, so the police said that you should call us when you find it, and then drive away.

Professor Shi took back his cell phone and updated it. He found that the engine had stopped, indicating that the car had been parked somewhere again, 4.3 miles from the display.

So Professor Shi and Xiao Wang began to repeat the simple but effective greedy search scheme in the morning. Soon they saw the hijacked vehicle at the Citgo gas station at 2801 W 87th St. The car is parked on the left side of the white car in the picture, double-flash, unable to see whether there is anyone in the car.


Drawing lessons from the previous experience, this time they drove into the gas station and stopped at the location of the black car in Turi to make sure they could see the hijacked vehicle. Then they dialed 911 again.

This time Professor Shi told the operator directly: I saw the hijacked vehicle, not far from me. There seemed to be someone in the car. They also had guns.

Sure enough, less than five minutes later, the first police car arrived. In the next few minutes, seven or eight police cars came to Hula and surrounded the gas station. The policemen came down wearing bullet-proof vests and putting their hands on the guns at their waists. A group of policemen approached the Mazda cautiously and quickly confirmed that no one was in the car.

So Professor Shi went over and opened the back box. He found his schoolbag, a camera bag with a SLR and several lenses, Mrs. Shi's bag, and a brand new pair of Nike boots without knowing who it was.

The missing items included multiple documents, a smell of marijuana in the car, and some food bags and coke cans left by the robbers in the back seat.

After reading this story, it is necessary to introduce Professor Shi's background.


Shi Yi Yu

Shi Yiyu (Ph. D.) is a lifelong associate professor and doctoral supervisor in the Department of Computer Science, Notre Dame University. He is also a lifelong associate professor in the Department of Electronics. He is the director of the Center for New Sustainable Artificial Intelligence and Obstetrics of the National Science Foundation of the United States. Former Assistant Professor, Doctoral Tutor, University of Missouri, Laura, and Deputy Director of the Network-based Software Systems Obstetrics Research Center of the National Science Foundation of the United States.

Professor Shi received his bachelor's degree in electronic engineering from Tsinghua University in 2005, his doctorate in electronic engineering from UCLA in 2009 and his postdoctoral research from Carnegie Mellon University in 2009-2010.

Professor Shi's current research direction is mainly the hardware implementation of artificial intelligence and its application in medical field. He has won the CAREER Award of the National Natural Fund of the United States, the IE Region Achievement Award for 5 people, the Carl St. Louis Academy of Sciences Invention Award, etc. and has been nominated for the best papers at many top international conferences in the field. He has won five U.S. invention patents (one won the IBM Patent Award in 2009 and one won the gold medal in Taipei International Expo); and has published more than 100 academic papers in important international research journals and conferences. He is currently the deputy Editor-in-Chief of the IEEE VLSI Circuits and System Letter, the ASSOCIATE Editor of the Journals of IEEE Trans. on CAD, ACM JETC, VLSI Integration, and Chair of the Education of ACM SIGDA.

Greedy algorithm is an algorithm that takes the best or the best (i.e. the most advantageous) choice in the current state in each step of selection, hoping to lead to the best or the best result.


Professor Huan Jun, director of Baidu Beijing Big Data Laboratory, believes that Professor Shi's greedy approach is a convex optimization problem, and he can always measure distance.

Professor Shi's algorithm, in short, reduces the distance at each step, so it's a greedy algorithm.

So, don't mess with algorithmic people!

China IT News APP

Download China IT News APP

Please rate this news

The average score will be displayed after you score.

Post comment

Do not see clearly? Click for a new code.

User comments