LeetCode Problem Of The Day

Over the past couple of years I have adopted a habit of completing the LeetCode “Problem of the Day” each morning, often as the first thing I do when I wake, or at least before I start work. I love this and it has made me much faster and more confident about the type of algorithms and data structures questions that frequent software engineering interviews.

Technically, LeetCode calls these “[Month] LeetCoding Challenge [Year]” as the screenshot I captured shows. The idea is to solve each problem on the calendar day that LeetCode posts it, and build a streak of consecutive days that I’ve solved the daily problem.

LeetCode being a business, they also sell “time travel certificates” that allow me “travel back in time” to solve a past day’s problem and keep a streak alive. They also provide one extra weekly problem to paid subscribers. I believe you can’t technically complete the monthly streak unless you become a paid subscriber and solve those.

I don’t worry about the streak mechanic, although I certainly don’t begrudge LeetCode the attempt to generate some cashflow from the service they provide. Sometimes I miss days, either because of travel or family or because the problem is legitimately too hard for me to solve. I just pick up the next day.

One of my favorite aspects is reviewing the official Solution explanation, or the user-generate discussion thread, after I’ve solved a problem myself. I gain a lot from reviewing other users’ code and comparing their solutions to mine, especially when my solution works but is slow. LeetCode times submissions and shows the result, unless the code is so inefficient that it triggers a “Time Limit Exceeded” error.

The rhythm of solving one data structures and algorithms problem every morning is a terrific routine for programming practice. There’s obviously a lot more to software engineering than compact, competitive programming-style and interview-style challenges. But I always feel like a musician practicing scales or a basketball player practicing free-throws – hardly the entire repertoire of the craft, but nonetheless a valuable way to practice by myself and develop skills that translate to other parts of the domain.

Lots Of Luminar

Introducing Iris on Vimeo

Luminar has been busy with a lot of announcements. Today, they reported preliminary (unaudited) 2020 financial results. 2020 revenue was $14 million, 2021 revenue is projected at $25-30 million, and the “forward-looking order book” is $1.3 billion. That’s an amazing growth curve, so much so that I’d like to understand the timeline and certainty of that $1.3 billion order book.

They also announced a big win this morning with SAIC, the Chinese automotive giant. SAIC will put Luminar’s Iris sensors in a large segment of its future vehicles.

Yesterday, Luminar published a high-quality 4-minute YouTube video entitled, “The Path to Series Production: Q1 Update.” That term – “series production” – is a phrase Luminar CEO Austin Russell emphasizes frequently, distinguishing Luminar from competitors who are still largely working on pilot projects with automakers.

Last week, Luminar held a joint event with Zenseact CEO Ödgärd Andersson to announce their partnership on full-stack self-driving software. Zenseact is Volvo’s self-driving spin-out, and Volvo is Luminar’s first and soonest major customer.

For all that, Luminar shares ended the day down about 4%. Tough crowd, Wall Street.

Automotive Regulation, Explained

The National Highway Traffic Safety Administration (NHTSA) recently provided “advanced notice of proposed rulemaking” (ANPRM) for an 18-page “proposed rule” titled, “Framework for Automated Driving System Safety.”

The ANPRM process, like many US government procedures, allows for public comments. In this case, the chairman of the National Transportation Safety Board (NTSB), Robert L. Sumwalt, III, posted a comment in the form of a 15-page letter, obliquely critical of NHTSA’s current approach to autonomous driving regulation (NTSB thinks NHTSA should regulate autonomous driving more). The Tesla Full Self-Driving beta looms large here.

I thought about writing a post on the merits of this particular exchange, and the proposals involved. I may still write about that. But I realized there was going to be a long wind-up about what these entities are and how they relate to each other.

I’m just going to let that wind-up eat the rest of this post. If what you really want right now is analysis of the NHTSA -NTSB spat, this isn’t going to be that, but here are some takes.


United States

The US has multiple automotive regulatory bodies, both at the federal level and the state level. The description I’ve heard is that, broadly speaking, the federal government regulates vehicles and the state governments regulate drivers. Of course, this distinction becomes less clear when the autonomous vehicle is also the driver.

Federal

Sticking with traditional, human-driven vehicles, the federal government regulates automobiles through (natch) the US Department of Transportation, newly and currently led by Secretary Mayor Pete. Matt Yglesias writes that most of the authority at DoT does not really accrue to the Secretary, but rather to bureaucracies that are nominally within DoT but in practice are largely autonomous.

National Highway Traffic Safety Administration

The specific bureaucracy in charge of regulating automobiles is the National Highway Traffic Safety Administration, “a multifaceted organization with a budget of $911 million and 626 full-time employees located throughout the country.”

The President appoints the Administrator of NHTSA, subject to the advice and consent of the Senate. This is part of what makes NHTSA (and many other agencies) semi-autonomous from their nominal umbrella Department. Secretary Buttigieg probably didn’t have much say in appointing the Administrator of NHTSA, nor is it likely that Secretary Buttigieg could fire the NHTSA Administrator (perhaps he could lobby the White House, though). In fact, currently, there does not appear to be a Senate-confirmed NHTSA Administrator (a common state of affairs for many federal bureaucracies). Jack Danielson is listed variously as the Acting Deputy Administrator, or the Executive Director.

Beyond staffing politics, NHTSA regulates several different aspects of automotive performance, especially safety and fuel economy. NHTSA regulates safety largely through Federal Motor Vehicle Safety Standards, a rulebook specifying requirements that vehicles sold in the US must meet. I heard that FMVSS compliance is largely conducted on the honor system, rather than through rigorous inspection and certification of every new vehicle model brought to market.

NHTSA also runs the US New Car Assessment Program (NCAP). This is the program you might have seen in car commercials, where a vehicle containing crash test dummies hurtles into a wall at 35mph. NCAP assigns front- and side-impact safety ratings to vehicles, based on a five-star scale.

Corporate Average Fuel Economy (CAFE) enforcement is another important NHTSA responsibility. Basically, automotive manufacturers are penalized for producing too many fuel-inefficient vehicles (largely trucks and SUVs). Consumers don’t have to directly pay penalties for purchasing fuel-inefficient vehicles, but presumably those fees are passed on, indirectly, by the manufacturers.

Other important NHTSA responsibilities include the collection of traffic data, and also purchasing a lot of advertisements encouraging people to drive safely and wear seatbelts. Indeed, advertising spend might actually be the majority of NHTSA’s budget.

More US Department of Transportation Administrations

The Federal Motor Carrier Safety Administration is to some extent the trucking analog to NHTSA. Its focus tends to be less on vehicles and more on policies applied to trucking companies to ensure that drivers are healthy and alert.

The Federal Highway Administration primarily funds the construction of highways, particularly US Interstate Highways, and is not especially involved with the vehicles that travel on them.

Similarly, the Federal Transit Administration exists principally to fund regional and local mass-transit systems.

National Transportation Safety Board

The National Transportation Safety Board sits outside of the Department of Transportation, as a wholly independent agency of the federal governments. Its primary role is investigative, and historically its domain has been aviation. NTSB came into existence due to concerns that it was a conflict of interest for the Federal Aviation Administration to investigate airplane crashes, since to an extent the FAA was investigating itself. The current chairman of the NTSB, Robert Sumwalt, III, comes from the aviation world.

Nonetheless, the NTSB has authority to investigate most modes of transportation, including all highway collisions.

Significantly, the NTSB has no regulatory authority nor ability to enforce policies. Based on its investigatory work, the NTSB may recommend safety regulations to agencies such as NHTSA, but those agencies can chose to accept, reject, or ignore NTSB recommendations.

States

Government in the United States takes the form of a federal republic, in which there is a kind of dual sovereignty shared by the national (“federal”) government and the state governments. All fifty states have some version of a state-level department of transportation, which also has regulatory authority over automotive vehicles.

Departments of Motor Vehicles

Within any given state Department of Transportation, there is typically a Department of Motor Vehicles (DMV). Different states have slightly different names – Arizona has a Motor Vehicle Division, Indiana has a Bureau of Motor Vehicles, and Washington has a Department of Licensing.

The primary responsibilities of the state-level DMVs are to license drivers and register vehicles. Driver’s licenses are typically granted through the completion of educational curricula and the passage of exams, which can be both written and practical. Vehicle registration largely amounts to issuing license plates, collecting taxes, and maintaining a database of which person owns which license plate.

DMVs have been the primary regulators of autonomous vehicles (AVs) in the US for several reasons:

  • Historically, DMVs have taken responsibility for certifying and licensing human drivers. In a sense, computers are just an extension of this responsibility.
  • In many cases, the underlying vehicle has already been approved by NHTSA as a human-driven vehicle. Changes to make the underlying vehicle autonomous typically relate to the autonomous driving system, not the vehicle platform.
  • AV testing is limited to a small minority of states, and there is relatively little interstate AV travel (yet). This makes it feasible to let those states handle regulation within their borders.
  • Both the Obama and Trump administrations largely took a “wait and see” approach to autonomous driving.

Other State Agencies

Particularly in California, which is both large and relatively heavily-regulated, other state agencies become involved in automotive regulation.

The California Air Resources Board (CARB) sets pollution standards for vehicles and vehicle fuel, above and beyond CAFE requirements. Because California is such a large portion of the overall US economy, automotive manufacturers will often apply CARB regulations nationwide, because that might be easier than having a separate California-only version of a vehicle.

The California Public Utilities Commission (CPUC) regulates taxis and ridesharing generally, including probably robotaxis. Since no commercial robotaxi service has yet launched in California, their authority in this area is unclear.

Police

In the US, police tend to be local government employees, although there is typically also a state-level police force charged with (among other responsibilities) enforcing driving laws on highways. Police are not, strictly speaking, regulators, but in practice they have a lot of discretion about whether and how to enforce traffic laws.

Many (most?) Americans are most likely to interact with police as a result of minor moving violations or other routine traffic stops. How this will change for vehicles without human drivers remains to be seen.

Europe

European automotive regulation happens primarily at the national level, although voluntary certification exists at the continent-wide level.

Euro NCAP

The European New Car Assessment Program (Euro NCAP) is similar to NHTSA’s NCAP. Both of these programs, along with similar programs in other regions, are part of the Global New Car Assessment Program (Global NCAP). Global NCAP is an attempt to synchronize vehicle safety assessment worldwide.

Unlike in the US, Euro NCAP is voluntary. Since individual countries certify vehicles within their own borders, Euro NCAP cannot and does not compel assessment. Nonetheless, many (most?) reputable vehicle manufacturers participate.

Euro NCAP is considered the most rigorous of all the different regional NCAPs, both because of Europe’s relative wealth and its safety mindset. NCAPs in less wealthy regions of the world tend toward less rigorous safety standards, in part due to what consumers in different parts of the world can afford to purchase.

TUV

Technischer Überwachungsverein (TUV) is a type of German organization that certifies vehicles and other machinery. There are three TUVs in Germany, each corresponding to a different geographic region. The name translates to “Technical Inspection Association.” These are non-governmental organizations.

As an American I have a hard time wrapping my head around what exactly TUVs do. My best model is that these are high-powered Consumer Reports-type organizations, but oriented more toward larger engineering projects and products.

TUV is an important safety evaluator in Europe, especially, for automotive components. US regulations and assessments tend to focus on holistically on the performance of the entire vehicle. TUV frequently drills down to evaluate specific parts from suppliers.

Motional recently worked with TUV SUD to determine their readiness for driverless testing.

China, India, And The World

As evidenced by my thin treatment of European automotive regulation, my knowledge is really limited outside the US. When it comes to China, India, and other regions, all I can really say is that there are lots of regional NCAPs.

I’m under-informed in this domain and need to educate myself. Send links if you have them.

TuSimple Plans Shanghai Operations

Of all the self-driving car companies with offices in both the US and China, TuSimple is one of the most bi-national. Many companies have offices in both nations, but seem to be clearly either a Chinese company with a US office, or vice versa. From the outside, at least, TuSimple seems to be pretty equally split.

That sentiment got a little bit of a boost with news that TuSimple has been approved to operate freight-carrying self-driving trucks in Shanghai. TuSimple is already operating in the southwestern United States. Now it may become one of the few companies operating self-driving cars internationally.

That geographic diversity has proven difficult to pull off, so TuSimple’s success seems like a real testament to their management team.

Cruise Acquires Voyage!

Cruise CTO and co-founder Kyle Vogt, left, with Voyage CEO and co-founder, Oliver Cameron, right

Voyage announced today that Cruise is acquiring us! I am excited to join one of the largest and most advanced companies working on self-driving cars.

A few months ago, I moved from Udacity to Voyage, in large part because so many of my former Udacity colleagues were at Voyage. Now we are moving together to Cruise, to work with a much larger team putting robotaxis on the road.

My brief time with Voyage has been delightful, and I hope to enjoy Cruise just as much. More to come!

“After being intimately involved with the AV industry for the last five years, I can say with certainty that Cruise — with its advanced self-driving technology, unique auto-maker partnerships, and all-electric purpose-built vehicle with no human controls — is poised to be the clear leader.”

Oliver Cameron

More Waymo Challenges!

Waymo has expanded their Open Dataset to include prediction data, and they’ve posed a new set of challenges for the public to tackle.

Motion prediction challenge: Given agents’ tracks for the past 1 second on a corresponding map, predict the positions of up to 8 agents for 8 seconds into the future.

Interaction prediction challenge: Given agents’ tracks for the past 1 second on a corresponding map, predict the joint future positions of 2 interacting agents for 8 seconds into the future.

Real-time 3D detection: Given lidar range images and their associated camera images, produce a set of 3D upright boxes for the objects in the scene, with a latency requirement.

Real-time 2D detection: Given a set of camera images, produce a set of 2D boxes for the objects in the scene, with a latency requirement.

What’s more, they published an academic paper describing how they automated the labeling of the data.

Submissions to the challenges are due on May 31.

Tesla Is Definitely Still Using Maps

For my latest Forbes article, I pondered Tesla’s use of maps, and how they communicate the need for maps to regulators and to the public.

Tesla’s use of pre-defined maps for its ADAS features has long be ambiguous and tied up in Elon Musk’s disdain for lidar, which is the principal tool for building high-definition maps.

Nonetheless, recently released communication between Tesla and the California Department of Motor Vehicles reveals that mapping is a central component of several Full Self-Driving features.

Read the whole thing.

Pythagorean Theorem

For the first fifteen years of my career in software, I barely used algebra. Web development requires plenty of abstract reasoning, but not higher math. Since working on autonomous vehicles, however, I constantly find myself revisiting topics I last touched in high school.

Pythagorean Theorem is a great example.

a*a + b*b = c*c

When on earth would you actually use this in “real life?” A few years ago I might have said never. Now I use it all the time.

Imagine I’m trying to calculate a vehicle’s acceleration, and the sensors tells me it’s accelerating 1 meter per second in the x-direction and 0.5 meters per second in the y-direction. What is the acceleration in the vehicle’s own frame of reference?

I’d use Pythagorean Theorem to find the answer. You can try it with an online calculator. What’d you get?

Tesla Autosteer Cut Accident Rates By 40% [Update: Maybe The Opposite!]

[Update: On Twitter, Michael DeKort points to an Ed Niedermeyer story in The Drive that suggests NHTSA’s data and analysis were flawed and Tesla Autosteer may actually have increased accidents.]

Yesterday I wrote that 2020 traffic deaths showed a big increase over previous years, probably due to distracted driver (cell phones). At the end of the post, I wondered whether advanced driver assistance systems (ADAS) are helping or hurting this situation.

I did some very light Internet searching today, and the most information I could find is this NHTSA report from 2016, which states:

“The data show that the Tesla vehicles crash rate dropped by almost 40 percent after Autosteer installation.”

In addition to this, I found some sporadic reports of Autopilot-related insurance discounts from Tesla owners and small insurance companies.

This isn’t a lot to go on — the data are dated (I forgot that “Autosteer” was a feature name), and mentioned off-hand in a NHTSA report that is really about AEB deployment. More importantly, there’s no data for ADAS options other than Tesla. Tesla is a small and controversial portion of the ADAS market.

But it’s the data I found so far.