Topic

Robot car virtual contest and demolition derby

A couple of weeks ago I wrote about the need for a good robocar driving simulator. Others have been on the track even earlier and are arranging a pair of robotic driving contests in simulator for some upcoming AI conferences.

The main contest is a conventional car race. It will be done in the TORCS simulator I spoke of, where people have been building robot algorithms to control race cars for some time, though not usually academic AI researchers. In addition, they’re adding a demolition derby which should be a lot of fun, though not exactly the code you want to write for safety.

This is, however, not the simulator contest I wrote about. The robots people write for use in computer racing simulators are given a pre-distilled view of the world. They learn exactly where the vehicle is, where the road edges are and where other cars are, without error. Their only concern is to drive based on the road and the physics of their vehicle and the track, and not hit things — or in the case of the derby, to deliberately hit things.

The TORCS engine is a good one, but is currently wired to do only an oval racetrack, and the maintainers, I am told, are not interested in having it support more complex street patterns.

While simulation in an environment where all the sensing problems are solved is a good start, a true robocar simulation needs simulated sensors — cameras, LIDAR, radar, GPS and the works — and then software that takes that and tries to turn it into a map of where the road is and where the vehicles and other things are. Navigation is also an important thing to work out. I will try to attend the Portland version of this conference to see this contest, however, as it should be good fun and generate interest.

Let me print my boarding pass long before my flight

I love online check-in, and printing your boarding pass at home to avoid doing anything but going to the gate at the airport. Airlines are even starting to do something I asked for many years ago and sending a boarding pass to the cell phone that can be held up to a screen for check-in.

But if they can’t do that, I want them to let me to print my boarding pass long before my flight. In particular, to print my return boarding pass when I print my outgoing one. That’s because I have a printer at home but often don’t have one on the road.

Of course, you can’t actually check in until close to the flight, so this boarding pass would be marked as preliminary, but still have bar codes identifying what they need to scan. On the actual day of the flight, I would check in from my phone or laptop, so they know I am coming to the plane. There’s no reason the old boarding pass’s bar codes can’t then be activated as ready to work. Sure, it might not know the gate, and the seat may even change, but such seat changes are rare and perhaps then I would need to go to a kiosk to swap the old pass for a new one. If the flight changes then I may also need to do the swap but the swap can be super easy — hold up old pass, get new one.

I could also get a short code to write on the pass when I do my same-day check-in, such code being usable to confirm the old pass has been validated.

Police robots everywhere?

It is no coincidence that two friends of mine have both founded companies recently to build telepresence robots. These are easy to drive remote control robots which have a camera and screen at head height. You can inhabit the robot, and drive it around a flat area and talk to people by videoconferencing. You can join meetings, go visit people or inspect a factory. Companies building these robots, initially at high prices, intend to sell them both to executives who want to remotely tour remote offices and to companies who want to give cheaper remote employees a more physical presence back at HQ.

There are also a few super-cheap telepresence robots, such as the Spykee, which runs Skype video conferencing and can be had for as low as $150. It’s not very good, and the camera is very low down, and there’s no screen, but it shows just how cheap such a product can get.

“Anybots” QA telepresence robot

When they get down to a price like that, it seems inevitable to me that we will see an emergency services robot on every block, primarily for use by the police. When there is a police, fire or ambulance call to an address, an officer could immediately connect to the robot on that block and drive it to the scene, to be telepresent. The robot would live in a small, powered protective closet either paid for by the city, but more likely just donated by some neighbour on the block who wants the fastest possible emergency response. Called into action, the robot’s garage door would open and the robot would drive out, and probably be at the location of the emergency within 60 to 120 seconds, depending on how densely they are placed. In the meantime actual first responders might also be on the way.

What could such a robot do?  read more »

Transit energy chart updated from latest DoE book

Back in 2008 I wrote a controversial article about whether green transit was a myth in the USA. Today I updated the main chart in that article based on new releases of the Department of Energy Transportation Energy Fact Book 2009 edition. The car and SUV numbers have stayed roughly the same (at about 3500 BTUs/passenger-mile for the average car under average passenger load.)

What’s new?

  • Numbers for buses are now worse at 4300. Source data predates the $4/gallon gas crisis, which probably temporarily improved it.
  • Light (capacity) rail numbers are significantly worse — reason unknown. San Jose’s Light rail shows modest improvement to 5300 but the overall average reported at 7600 is more than twice the energy of cars!
  • Some light rail systems (See Figure 2.3 in Chapter 2) show ridiculously high numbers. Galveston, Texas shows a light rail that takes 8 times as much energy per passenger as the average SUV. Anybody ridden it and care to explain why its ridership is so low?
  • Heavy rail numbers also worsen.
  • Strangely, average rail numbers stay the same. This may indicate an error in the data or a change of methodology, because while Amtrak and commuter rail are mildly better than the average, it’s not enough to reconcile the new average numbers for light and heavy rail with the rail average.
  • I’ve made a note that the electric trike figure is based on today’s best models. Average electric scooters are still very, very good but only half as good as this.
  • I’ve added a figure I found for the East Japan railway system. As expected, this number is very good, twice as good as cars, but suggests an upper bound, as the Japanese are among the best at trains.
  • I removed the oil-fueled-agriculture number for cyclists, as that caused more confusion than it was worth.
  • There is no trolley bus number this year, so I have put a note on the old one.
  • It’s not on the chart, but I am looking into high speed rail. Germany’s ICE reports a number around 1200 BTU/PM. The California HSR project claims they are going to do as well as the German system, which I am skeptical of, since it requires a passenger load of 100M/year, when currently less than 25M fly these routes.

Everybody is your 16th cousin

In my article two weeks ago about the odds of knowing a cousin I puzzled over the question of how many 3rd cousins a person might have. This is hard to answer, because it depends on figuring out how many successful offspring per generation the various levels of your family (and related families) have. Successful means that they also create a tree of descendants. This number varies a lot among families, it varies a lot among regions and it has varied a great deal over time. An Icelandic study found a number of around 2.8 but it’s hard to conclude a general rule. I’ve used 3 (81 great-great-grandchildren per couple) as a rough number.

There is something, however, that we can calculate without knowing how many children each couple has. That’s because we know, pretty accurately, how many ancestors you have. Our number gets less accurate over time because ancestors start duplicating — people appear multiple times in your family tree. And in fact by the time you go back large numbers of generations, say 600 years, the duplication is massive; all your ancestors appear many times.

To answer the question of “How likely is it that somebody is your 16th cousin” we can just look at how many ancestors you have back there. 16th cousins share with you a couple 17 generations ago. (You can share just one ancestor which makes you a half-cousin.) So your ancestor set from 17 generations ago will be 65,536 different couples. Actually less than that due to duplication, but at this level in a large population the duplication isn’t as big a factor as it becomes later, and if it does it’s because of a closer community which means you are even more related.

So you have 65K couples and so does your potential cousin. The next question is, what is the size of the population in which they lived? Well, back then the whole world had about 600 million people, so that’s an upper bound. So we can ask, if you take two random sets of 65,000 couples from a population of 300M couples, what are the odds that none of them match? With your 65,000 ancestors being just 0.02% of the world’s couples, and your potential cousin’s ancestors also being that set, you would think it likely they don’t match.

Turns out that’s almost nil. Like the famous birthday paradox, where a room of 30 people usually has 2 who share a birthday, the probability there is no intersection in these large groups is quite low. it is 99.9999% likely from these numbers that any given person is at least a 16th cousin. And 97.2% likely that they are a 15th cousin — but only 1.4% likely that they are an 11th cousin. It’s a double exponential explosion. The rough formula used is that the probability of no match will be (1-2^C/P)^(2^C) where C is the cousin number and P is the total source population. To be strict this should be done with factorials but the numbers are large enough that pure exponentials work.

Now, of course, the couples are not selected at random, and nor are they selected from the whole world. For many people, their ancestors would have all lived on the same continent, perhaps even in the same country. They might all come from the same ethnic group. For example, if you think that all the ancestors of the two people came from the half million or so Ashkenazi Jews of the 18th century then everybody is a 10th cousin.

Many populations did not interbreed much, and in some cases of strong ethnic or geographic isolation, barely at all. There are definitely silos, and they sometimes existed in the same town, where there might be far less interbreeding between races than among races. Over time, however, the numbers overwhelm even this. Within the close knit communities, like say a city of 50,000 couples who bred mostly with each other, everybody will be a 9th cousin.

These numbers provide upper bounds. Due to the double exponential, even when you start reducing the population numbers due to out-breeding and expansion, it still catches up within a few generations. This is just another measure of how we are all related, and also how meaningless very distant cousin relationships, like 10th cousins, are. As I’ve noted in other places, if you leave aside the geographic isolation that some populations lived in, you don’t have to go back more more than a couple of thousand years to reach the point where we are not just all related, but we all have the same set of ancestors (ie. everybody who procreated) just arranged in a different mix.

The upshot of all this: If you discover that you share a common ancestor with somebody from the 17th century, or even the 18th, it is completely unremarkable. The only thing remarkable about it is that you happened to know the path.

Towards a more secure web, and better TLS

Today an interesting paper (written with the assistance of the EFF) was released. The authors have found evidence that governments are compromising trusted “certificate authorities” by issuing warrants to them, compelling them to create a false certificate for a site whose encrypted traffic they want to snoop on.

That’s just one of the many ways in which web traffic is highly insecure. The biggest reason, though, is that the vast majority of all web traffic takes place “in the clear” with no encryption at all. This happens because SSL/TLS, the “https” system is hard to set up, hard to use, considered expensive and subject to many false-alarm warnings. The tendency of security professionals to deprecate anything but perfect security often leaves us with no security at all. My philosophy is different. To paraphrase Einstein:

Ordinary traffic should be made as secure as can be made easy to use, but no more secure

In this vein, I have prepared a new article on how to make the web much more secure, and it makes sense to release it today in light of the newly published threat. My approach, which calls for new browser behaviour and some optional new practices for sites, calls for the following:

  • Make TLS more lightweight so that nobody is bothered by the cost of it
  • Automatic provisioning (Zero UI) for self-signed certificates for domains and IPs.
  • A different meaning for the lock icon: Strong (Locked), Ordinary (no icon) and in-the-clear (unlocked).
  • A new philosophy of browser warnings with a focus on real threats and on changes in security, rather than static states deemed insecure.
  • A means so sites can provide a file with advisories for browsers about what warnings make sense at this site.

There is one goal in mind here: The web must become encrypted by default, with no effort on the part of site operators and users, and false positive warnings that go off too frequently and make security poor and hard to use must be eliminated.

If you have interest in browser design and security policy I welcome your comments on A new way to secure the web.

The Robocar Babysitter and revolutions in child-watching

Watching and managing children is one of the major occupations of the human race. A true robot babysitter is still some time in the future, and getting robocars to the level that we will trust them as safe to carry children is also somewhat in the future, but it will still happen much sooner.

Today I want to explore the implications of a robocar that is ready to safely carry children of certain age ranges. This may be far away because people are of course highly protective of their children. They might trust a friend to drive a child, even though human driving records are poor, because the driver is putting her life on the line just as much as the child’s, while the robot is just programmed to be safe, with no specific self-interest.

A child’s robocar can be designed to higher safety standards than an adult’s, with airbags in all directions, crumple zones designed for a single occupant in the center and the child in a 5-point seatbelt. As you know, with today’s modern safety systems, racecar drivers routinely walk away from crashes at 150mph. Making a car that won’t hurt the child in a 40mph crash is certainly doable, though not without expense. A robocar’s ability to anticipate an accident might even allow it to swivel the seat around so that the child’s back is to the accident, something even better than an airbag.

The big issue is supervision of smaller children. It’s hard to say what age ranges of children people might want to send via robocar. In some ways infants are easiest, as you just strap them in and they don’t do much. All small children today are strapped in solidly, and younger ones are in a rear facing seat where they don’t even see the parent. (This is now recommended as safest up to age 4 but few parents do that.) Children need some supervision, though real problems for a strapped in child are rare. Of course, beyond a certain age, the children will be fully capable of riding with minimal supervision, and by 10-12, no direct supervision (but ability to call upon an adult at any time.)  read more »

Poor Man's Teleporter

One of the things that’s harder to predict about robocars is what they will mean for how cities are designed and how they evolve. We’re notoriously bad at predicting such things, but it is still tempting.

A world of robocars offers the potential for something I am dubbing the “poor man’s teleporter.” That’s a fleet of comfortable robotaxis that are, while you are in them, a fully functional working or relaxing environment. Such robotaxis would have a desk and large screen and very high speed wireless net connection. They have a comfy reclining chair (or bed) and anything else you need from the office environment. (Keyboards and mice are problematic, as I have discussed elsewhere, but there may be ways to solve that.)

The robotaxi will deliberately pick the most comfortable route for a trip, with few turns, few stops and gentle acceleration. It will gimbal in corners and have an active suspension system eliminating bumps. The moment you enter it, your desktop could appear on the screen, copied from the desk you left (thanks to communication with one of your wearable devices, probably.) You can do high quality videoconferencing, work on the net, or just watch a video or read a book — the enclosed book reader could be set to the page you were last reading elsewhere. If you work in a building with a lobby, the electric robotaxi could enter the lobby and meet you right at the elevator. It might even go vertical and ride up the elevator to get you during less busy times. (For some real science fiction, the robotaxis in Minority Report somehow climbed the buildings and parked in people’s homes.)

For many it would be as though they had not left their desks. Almost all the trip will be productive time. As such, while people won’t want to spend forever in the car, many might find distance and trip time to not be particularly important, at least not for trips around town during the workday. While everybody wants to get home to family sooner, even commute times could become productive times with employers who let the employee treat the travel time as work time. Work would begin the moment you stepped into the car in the morning.

We’ve seen a taste of this in Silicon Valley, as several companies like Google and Yahoo run a series of commute vans for their employees. These vans have nice chairs, spaces for laptops and wireless connectivity into the corporate network. Many people take advantage of these vans and live in places like San Francisco, which may be an hour-long trip to the office. The companies pay for the van because the employees start the workday when they get on it.

This concept will continue to expand, and I predict it will expand into robocars. The question is, what does it mean to how we live if we eliminate the time-cost of distance from many trips? What if we started viewing our robotaxis as almost like a teleporter, something that takes almost no time to get us where we want to go? It’s not really no-time, of course, and if you have to make a meeting you still have to leave in time to get there. It might be easier for some to view typical 15 minute trips around a tight urban area as no-time while viewing 30-60 minute trips as productive but “different time.”

Will this make us want to sprawl even more, with distance not being important? Or will we want to live closer, so that the trips are more akin to teleportation by being productive, short and highly predictable in duration? It seems likely that if we somehow had a real Star-Trek style transporter, we might all live in country homes and transport on demand to where the action is. That’s not coming, but the no-lost-time ride is. We might not be able to afford a house on the nice-walkable-shops-and-restaurants street, but we might live 2 miles from it and always be able to get to it, with no parking hassle, in 4 minutes of productive time.

What will the concept of a downtown mean in such a world? “Destination” retailers and services, like a movie house, might decide they have no real reason to be in a downtown when everybody is coming by robotaxi. Specialty providers will also see no need to pay a premium to be in a downtown. Right now they don’t get walk-by traffic, but they do like to be convenient to the customers who seek them out. Stores that do depend on walk-by traffic (notably cafes and many restaurants) will want to be in places of concentration and walking.

But what about big corporate offices that occupy the towers of our cities? They go there for prestige, and sometimes to make it easy to have meetings with other downtown companies. They like having lots of services for their employees and for the business. They like being near transit hubs to bring in those employees who like transit. What happens when many of these needs go away?

For many people, the choice of where to live is overwhelmingly dominated by their children — getting them nice, safe neighbourhoods to play in, and getting them to the most desired schools. If children can go to schools anywhere in a robocar, how does that alter the equation? Will people all want bigger yards in which to cacoon their children, relying on the robocar to take the children to play-dates and supervised parks? Might they create a world where the child goes into the garage, gets in the robocar and tells it to go to Billy’s house, and it deposits the child in that garage, never having been outside — again like a teleporter to the parents? Could this mean a more serious divorce between community and geography?

While all this is going on, we’re also going to see big strides in videoconferencing and virtual reality, both for adults, and as play-spaces for adults and children. In many cases people will be interacting through a different sort of poor man’s teleporter, this one taking zero time but not offering physical contact.

Clearly, not all of these changes match our values today. But what steps that make sense could we actually take to promote our values? It doesn’t seem possible to ban the behaviours discussed above, or even to bend them much. What do you think the brave new city will look like?

More notes:

It is often said that cars caused the suburbanization of cities. However, people didn’t decide they wanted a car lifestyle and thus move where they could drive more. They sought bigger lots and yards, and larger detached houses. They sought quieter streets. While it’s not inherent to suburbs, they also sought better schools for kids and safer neighbourhoods. They gave up having nearby shops and restaurants and people to get those things, and accepted the (fairly high) cost of the car as part of the price. Most often for the kids. Childless and young people like urban life; the flight to the suburbs was led by the parents.

This doesn’t mean they stopped liking the aspects of the “livable city.” Having stuff close to you. Having your friends close to you. Having pleasant and lively spaces to wander, and in which you regularly see your friends and meet other people. Walking areas with interesting shops and restaurants and escape from the hassles of parking and traffic. They just liked the other aspects of sprawl more.

They tried to duplicate these livable areas with shopping malls. But these are too sterile and corporate — but they are also climate controlled and safer and caused the downfall of many downtowns. Then big box stores, more accessible from the burbs, kept at that tack.

The robotaxi will allow people to get more of what they sought from the “livable city” while still in sprawl. It will also let them get more of what they sought from the suburbs, in terms of safety and options for their children. They may still build pleasant pedestrian malls in which one can walk and wander among interesting things, but people who live 5 miles away will be able to get to them in under 10 minutes. They will be delivered right into the pedestrian zone, not to a sprawling parking lot. They won’t have to worry about parking, and what they buy could be sent to their home by delivery robot — no need to even carry it while walking among shops. They will seek to enjoy the livable space from 5 miles away the same way that people today who live 4 blocks away enjoy those spaces.

But there’s also no question that there will continue to be private malls trying to meet this need. Indeed the private malls will probably offer free or validated robotaxi service to the mall, along with delivery, if robotaxi service is as cheap as I predict it can be. Will the public spaces, with their greater variety and character be able to compete? They will also have weather and homeless people and other aspects of street life that private malls try to push away.

The arrival of the robocar baby-sitter, which I plan to write about more, will also change urban family life. Stick the kid in the taxi and send him to the other parent, or a paid sitter service, all while some adult watches on the video and redirects the vehicle to one of a network of trusted adults if some contingency arises. Talk about sending a kid to a time-out!

An open source licence for FOSS platforms only

Here’s a suggestion that will surely rankle some in the free software/GPL community, but which might be of good benefit to the overall success of such systems.

What I propose is a GPL-like licence under which source code could be published, but which forbids effectively one thing: Work to make it run on proprietary operating systems, in particular Windows and MacOS.

The goal would be to allow the developers of popular programs for Windows, in particular, to release their code and allow the FOSS community to generate free versions which can run on Linux, *BSD and the like. Such companies would do this after deciding that there isn’t enough market on those platforms to justify a commercial venture in the area. Rather than, as Richard Stallman would say, “hoarding” their code, they could release it in this fashion. However, they would not fear they were doing much damage to their market on Windows. They would have to accept that they were disclosing their source code to their competitors and customers, and some companies fear that and will never do this. But some would, and in fact some already have, even without extra licence protection.

An alternate step would be to release it specifically so the community and make sure the program runs under WINE, the Windows API platform for Linux and others. Many windows programs already run under WINE, but almost all of them have little quirks and problems. If the programs are really popular, the WINE team patches WINE to deal with them, but it would be much nicer if the real program just got better behaved. In this case, the licence would have some rather unusual terms, in that people would have to produce versions and EXEs that run only under WINE — they would not run on native Windows. They could do this by inserting calls to check if they are running on WINE and aborting, or they could do something more complex like make use of some specific APIs added to WINE that are not found in Windows. Of course, coders could readily remove these changes and make binaries that run on Windows natively, but coders can also just pirate the raw Windows binaries — both would be violations of copyright, and the latter is probably easier to do.  read more »

Graphic with traffic death stats

Here’s a nice graphic showing traffic deaths around the world. Of course, all these numbers are going to drop over the next 10 years thanks to various collision avoidance and accident survival technologies in cars, and eventually, we hope, robocars.

PETA prize should start with eggs and dairy

I have some admiration for the PETA prize for vat-grown chicken. A winner of this prize would strongly promote PETA’s ethical goals, as well as many environmental goals, for the livestock industry is hugely consumptive of land, as it takes far more grain to feed animals than it takes to feed us, per calorie.

One part I admire, in a sardonic way, is the way it will make some people’s heads explode. The environmental destruction of livestock, and the cruelty, are well established. However many of the people who believe that most fervently also are very suspicious of synthetic foods, especially at this level. They would never say it, but they sometimes take actions which amount to choosing the starvation of people over the introduction of GMOs in the food supply. Not that the latter does not have its risks and unanswered questions, but that the costs are so high. PETA’s vat-grown chicken will cause massive debate when it comes.

But the contest is too hard (and has a 2010 deadline that seems designed to be impossible.) It requires a meat that people can’t tell from chicken that matches the market price of chicken and can sell. Oddly, it doesn’t require that the process be more efficient than chicken factory farms in terms of energy or land, though the cost pushes that way. But reproducing the texture and structure of chicken is a hard problem. Current work on vat-grown meat suggests less textured versions (for use in sausage and ground meat forms) will come first.

So I would propose a lesser prize, the production of vat-grown egg white, egg yolk and/or milk. As liquids, the task is probably an easier one. And these products have so many uses in foods, even if you can’t make something that fries up like an egg.

Of course vegetarians (as opposed to vegans) eat eggs and diary, though the PETA variety of vegetarian will insist these products come from humane farms, with free range animals, no hormones and no forced production. The agribusiness dairy and egg farms are not this way, they will point out — and they also consume a lot of land and generate lots of methane. And others will point out that overuse of eggs and dairy has health issues. But it’s a real prize.

The other way I would make their prize more winnable (if that’s their goal) would be to remove the requirement of of being indistinguishable. Instead, I would make the creation of a superior product qualify for victory. Instead of having an independent panel say “I can’t believe it’s not chicken,” I think it would be sufficient to have them say, “This is not chicken, but I like it as much or better than chicken as a meat.” And to prove this the market, where people are buying it instead of the equivalent bird. It’s true that an exact duplicate would have a faster adoption curve, but the wholly new food would get there eventually if people found it tasty. Tofu is tasty but chicken eaters don’t say they prefer it to chicken.

With eggs and dairy I think a perfect reproduction is more possible, in that you “just” have to duplicate the mammary tissue that produces the milk, for example. And this must be living, which may be a lot harder than the vat grown meat which may never fully be classed as living tissue. But my intuition says it will be easier, and fairly dramatic in effect.

Needed: An open robocar driving simulator. Here's how.

I was recently approached by a programmer named Keith Curtis, formerly at Microsoft and now a FOSS devotee. He wants to develop a driving simulator for testing robocar systems. I think this is a very worthwhile idea — sort of a “Second Life” for robots. We have a head start — the world of racecar video games has already done a lot of the legwork to simulate driving, and there are two open source car racing systems.

A good simulator would bring some tremendous benefits to robocar development.

  1. Anybody, even a solo hacker in their basement, could develop and test robocar software on the cheap, and with no cost and risk from crashes. Small teams, perhaps working in car-less garages, could contribute greatly to the field.
  2. Testing could go faster, and include regular exposure to extreme situations not often found in the real world, like crazy drivers, strange hazards, map errors, sensor failures and more.
  3. Simulator testing allows the creation of new sensors which are plausible, but too expensive or too far in the future to work with in the real world. It allows teams to say, “What if we had 1cm accurate GPS? What if we had 180 line LIDAR to 100m?” and see if they can build robocar controls to use it.
  4. Robocar contests could be held in simulation, on the cheap and with no physical risk. The winners could then get funding to build real-world vehicles to race for a bigger prize.
  5. The simulator APIs for car controls and sensors can become prototype APIs for real-world interfaces, allowing easy testing and switching.

Of course, robocar simulation is nothing new. Several teams in the DARPA challenges built simulators to try out ideas. These remained proprietary efforts. Road simulation is also frequently used for traffic simulators. An open simulator would be shared, and the community (and not just the robocar development community) could contribute terrain, streets, sensors and simulators for elements such as pedestrians, human driven cars, blowing trash and new sensors, to name just a few.

Our wonderful new fast GPUs will be able to generate camera views anywhere in the 3D world for those working on machine vision. Simulating LIDAR, radar, ultrasound, odometry, accelerometers etc. is not yet done in car racing games but these things should not be hard to add. Indeed, any company selling a sensor would be well advised to build a simulated version of it. And people hacking at home love to make 3-D maps of terrain. Existing real terrain models could be imported, or new ones made by driving around with LIDAR on real streets.

To explore this more I have written a new article on how to build a robocar driving simulator where I also point to an up and coming open source simulator called “Rigs of Rods” which actually simulates the vehicles at the physics level, treating them as a network of many connected parts.

The robocar world needs somebody ready to fun the kick-starting of such a simulator, and possibly some contests within it.

Haplogroups, Haplotypes and genealogy, oh my

I received some criticism the other day over my own criticism of the use of haplogroups in genealogy — the finding and tracing of relatives. My language was imprecise so I want to make a correction and explore the issue in a bit more detail.

One of the most basic facts of inheritance is that while most of your DNA is a mishmash of your parents (and all their ancestors before them) two pieces of DNA are passed down almost unchanged. One is the mitochondrial DNA, which is passed down from the mother to all her children. The other is the Y chromosome, which is passed down directly from father to son. Girls don’t get one. Most of the mother’s X chromosome is passed down unchanged to her sons (but not her daughters) but of course they can’t pass it unchanged to anybody.

This allow us to track the ancestry of two lines. The maternal line tracks your mother, her mother, her mother, her mother and so on. The paternal line tracks your father, his father and so on. The paternal line should, in theory, match the surname, but for various reasons it sometimes doesn’t. Females don’t have a Y, but they can often find out what Y their father had if they can sequence a sample from him, his sons, his brothers and other male relatives who share his surname.

The ability to do this got people very excited. DNA that can be tracked back arbitrarily far in time has become very useful for the study of human migrations and population genetics. The DNA is normally passed down completely but every so often there is a mutation. These mutations, if they don’t kill you, are passed down. The various collections of mutations are formed into a tree, and the branches of the tree are known as haplogroups. For both kinds of DNA, there are around a couple of hundred haplogroups commonly identified. Many DNA testing companies will look at your DNA and tell you your MTDNA haplogroup, and if male, your Y haplogroup.  read more »

The privacy risks of genetic genealogy (23andMe part 2)

Last week, I wrote about interesting experiences finding Cousins who were already friends via genetic testing. 23andMe’s new “Relative Finder” product identifies the other people in their database of about 35,000 to whom you are related, guessing how close. Surprisingly, 2 of the 4 relatives I made contact with were already friends of mine, but not known to be relatives.

Many people are very excited about the potential for services like Relative Finder to take the lid off the field of genealogy. Some people care deeply about genealogy (most notably the Mormons) and others wonder what the fuss is. Genetic genealogy offers the potential to finally link all the family trees built by the enthusiasts and to provably test already known or suspected relationships. As such, the big genealogy web sites are all getting involved, and the Family Tree DNA company, which previously did mostly worthless haplogroup studies (and more useful haplotype scans,) is opening up a paired-chromosome scan service for $250 — half the price of 23andMe’s top-end scan. (There is some genealogical value to the deeper clade Y studies FTDNA does, but the Mitochondrial and 12-marker Y studies show far less than people believe about living relatives. I have a followup post about haplogroups and haplotypes in genealogy.) Note that in March 2010, 23andMe is offering a scan for just $199.

The cost of this is going to keep decreasing and soon will be sub-$100. At the same time, the cost of full sequencing is falling by a factor of 10 every year (!) and many suspect it may reach the $100 price point within just a few years. (Genechip sequencing only finds the SNPs, while a full sequencing reads every letter (allele) of your genome, and perhaps in the future your epigenome.

Discover of relatives through genetics has one big surprising twist to it. You are participating in it whether you sign up or not. That’s because your relatives may be participating in it, and as it gets cheaper, your relatives will almost certainly be doing so. You might be the last person on the planet to accept sequencing but it won’t matter.  read more »

Terror and security

One of the world’s favourite (and sometimes least favourite) topics is the issue of terrorism and security. On one side, there are those who feel the risk of terrorism justifies significant sacrifices of money, convenience and civil rights to provide enough security to counter it. That side includes both those who honestly come by that opinion, and those who simply want more security and feel terrorism is the excuse to use to get it.

On the other side, critics point out a number of counter arguments, most of them with merit, including:

  • Much of what is done in the name of security doesn’t actually enhance it, it just gives the appearance of doing so, and the appearance of security is what the public actually craves. This has been called “Security Theatre” by Bruce Schneier, who is a friend and advisor to the E.F.F.
  • We often “fight the previous war,” securing against the tactics of the most recent attack. The terrorists have already moved on to planning something else. They did planes, then trains, then subways, then buses, then nightclubs.
  • Terrorists will attack where the target is weakest. Securing something just makes them attack something else. This has indeed been the case many times. Since everything can’t be secured, most of our efforts are futile and expensive. If we do manage to secure everything they will attack the crowded lines at security.
  • Terrorists are not out to kill random people they don’t know. Rather, that is their tool to reach their real goal: sowing terror (for political, religious or personal goals.) When we react with fear — particularly public fear — to their actions, this is what they want, and indeed what they plan to achieve. Many of our reactions to them are just what they planned to happen.
  • Profiling and identity checks seem smart at first, but careful analysis shows that they just give a more free pass to anybody the terrorists can recruit whose name is not yet on a list, making their job easier.
  • The hard reality is, that frightening as terrorism is, in the grand scheme we are for more likely to face harm and death from other factors that we spend much less of our resources fighting. We could save far more people applying our resources in other ways. This is spelled out fairly well in this blog post.

Now Bruce’s blog, which I link to above, is a good resource for material on the don’t-panic viewpoint, and in fact he is sometimes consulted by the TSA and I suspect they read his blog, and even understand it. So why do we get such inane security efforts? Why are we willing to ruin ourselves, and make air travel such a burden, and strip ourselves of civil rights?

There is a mistake that both sides make, I think. The goal of counter-terrorism is not to stop the terrorists from attacking and killing people, not directly. The goal of counter-terrorism is to stop the terrorists from scaring people. Of course, killing people is frightening, so it is no wonder we conflate the two approaches.  read more »

The odds of knowing your cousins: 23andme Part 1

Bizarrely, Jonathan Zittrain turns out to be my cousin — which is odd because I have known him for some time and he is also very active in the online civil rights world. How we came to learn this will be the first of my postings on the future of DNA sequencing and the company 23andMe.

(Follow the genetics for part two and other articles.)

23andMe is one of a small crop of personal genomics companies. For a cash fee (ranging from $400 to $1000, but dropping with regularity) you get a kit to send in a DNA sample. They can’t sequence your genome for that amount today, but they can read around 600,000 “single-nucleotide polymorphisms” (SNPs) which are single-letter locations in the genome that are known to vary among different people, and the subject of various research about disease. 23andMe began hoping to let their customers know about how their own DNA predicted their risk for a variety of different diseases and traits. The result is a collection of information — some of which will just make you worry (or breathe more easily) and some of which is actually useful. However, the company’s second-order goal is the real money-maker. They hope to get the sequenced people to fill out surveys and participate in studies. For example, the more people fill out their weight in surveys, the more likely they might notice, “Hey, all the fat people have this SNP, and the thin people have that SNP, maybe we’ve found something.”

However, recently they added a new feature called “Relative Finder.” With Relative Finder, they will compare your DNA with all the other customers, and see if they can find long identical stretches which are very likely to have come from a common ancestor. The more of this they find, the more closely related two people are. All of us are related, often closer than we think, but this technique, in theory, can identify closer relatives like 1st through 4th cousins. (It gets a bit noisy after this.)

Relative Finder shows you a display listing all the people you are related to in their database, and for some people, it turns out to be a lot. You don’t see the name of the person but you can send them an E-mail, and if they agree and respond, you can talk, or even compare your genomes to see where you have matching DNA.

For me it showed one third cousin, and about a dozen 4th cousins. Many people don’t get many relatives that close. A third cousin, if you were wondering, is somebody who shares a great-great-grandparent with you, or more typically a pair of them. It means that your grandparents and their grandparents were “1st” cousins (ordinary cousins.) Most people don’t have much contact with 3rd cousins or care much to. It’s not a very close relationship.

However, I was greatly shocked to see the response that this mystery cousin was Jonathan Zittrain. Jonathan and I are not close friends, more appropriately we might be called friendly colleagues in the cyberlaw field, he being a founder of the Berkman Center and I being at the EFF. But we had seen one another a few times in the prior month, and both lectured recently at the new Singularity University, so we are not distant acquaintances either. Still, it was rather shocking to see this result. I was curious to try to figure out what the odds of it are.  read more »

Placing camps at Burning Man

One of the toughest challenges the Burning Man staff face is placing all the camps in the city. This stopped being an anarchy long ago, and the city is mapped and each camp given a precise area. The city has various “premium” locations which are valued in part for being close to things but mainly because they are high traffic for camps showing off interesting art or interactivity. Far more camps want to be in the premium locations than there is room, and almost everybody serious wants to be pre-placed somewhere so they can plan in advance and not have to race in the land-rush when the event officially opens.

(Some people like the land-rush. While you will not get a spot very close to the Esplanade or be able to be on the maps and calendars by address, you will get a bigger space for your group, because it’s “take what you dare.”)

Camps submit applications (this year by the start of May) describing the contribution they will offer the city, where they would like to be, and how much space they need. A team of placers (mostly volunteers with a few paid leaders) try to allocate the camps. They try to be fair, but the process is largely opaque, so any biases and mistakes are not generally visible to the community.

The process takes time, and the placement last year was announced to the community in early August, just a few weeks before the event. Camps are told only their approximate street location, and their dimensions. For reasons few have been able to fathom, the actual precise map, showing who is on corners and who is next to whom, is kept secret until the event itself. Many factors go into the decision, including camp density, past reputations, the various prime locations available, camps that want or don’t wan’t to be next to other camps, loudness and quality and interactivity of the art in the camp.

In 2009, the placers decided something which was a fairly big surprise to the community. They decided not to place around 120 of the camps that applied at all. Those camps were left to the land-rush, which meant a few distressing things for them:

  • They could not arrive in the city before the opening to set up; some had rather extensive structures to build.
  • They could not know where they would be in advance, so they could not tell their address to people in advance, or put it in the city calendar which is handed out at the gate.

The placement team decided not to place these camps because they did not want to find themselves placing the majority of the city. They wanted the city to retain some randomness and made a decision that only a limited fraction of the city would be subject to mapping in advance. If too many camps applied, those who did not make the cut would not be placed. This decision caused some controversy, and there are arguments for both sides. In addition to the non-placements, there were also many camps surprised by their placement (usually negatively) and, as would be expected in any large volunteer effort, a modest number of mistakes.  read more »

Olympic sports and failure

I wanted to post some follow-up to my prior post about sports where the contestants go to the edge and fall down. As I see it, the sports fall into the following rough classes:

  1. You push as hard as you can. The athlete who does the best — goes higher, stronger, faster — wins. The 100 metres is a perfect example.
  2. You push hard, but you must make judgments as you compete, such as how hard to push, when to pass etc. If you judge incorrectly, it lowers your final performance, but only modestly.
  3. You must judge your abilities and the condition of the course and your equipment, and choose what is difficult enough to score well, but which you can be confident you will execute. To win, you must skate (literally or figuratively) close to the edge of what you can do. If you misjudge, or have bad luck, you are penalized significantly, and will move from 1st place to the rear of the pack.

My main concern is with sports in the third group, like figure skating, half-pipe and many others, including most of the judged sports with degrees of difficulty. The concern is that sudden shift from leader to loser because you did what you are supposed to do — go close to the edge. Medals come from either being greatly superior, knowing your edge very well, which is the intention, or from being lucky that particular day — which I think is not the intention.

Many sports seek to get around this. In high jump and pole vault, you just keep raising the bar until you can’t get over it, and somebody gets over the highest bar. This is a good system, but difficult when a sport takes a long time or is draining to do even once. You could do a figure skating contest where they all keep trying more and more difficult moves until they all fail but one, but it would take a long time, be draining, and cause injuries as there is no foam pit like in high jump.

Other sports try to solve this by letting you do 2 or more runs, and taking the best run. This is good, but we also have an instinct that the person who can do it twice is better than the one who did it once and fell down the other time. Sports that sum up several times demand consistent performance, which is good, but in essence they also put a major punishment on a single failure, perhaps an even greater one. This approach requires you be a touch conservative, just under your edge, so you know you will deliver several very good runs, and beat somebody who dares beyond their ability, but falls in one or more runs. At least it reduces the luck.

The particular problem is this. “Big failure” sports will actually often give awards either to a top athlete who got a good run, or to the athlete who was more conservative in choosing what to do, and thus had a very high probability of a clean run. Fortunately this will not happen too often, as one of the top tier who went-for-broke will have that clean run and get 1st place. But the person who does that may not be the one who is overall most capable.

Imagine if high jump were done with each competitor choosing what height they wanted the bar to be at in advance, and getting one try at it, and getting a medal if it’s the highest, but nothing if they miss.

The sports like short-track speed skating, which are highly entertaining, have this problem in spades, for athletes who wipe out can also impede other athletes. While the rules try to make it up to the athlete who was knocked out, they have a hard time doing this perfectly. For example in the semi-finals of short-track, if you get knocked out while you were in 3rd, you are not assured to get a consolation qualification even if you were just about to try for 2nd with the strength you were saving.

In some cases the chaos is not going away because they know audiences like it. Time trials are the purest and fairest competition in most cases but are dead-boring to watch.

Curling is the best Olympic sport

Some notes from the bi-annual Olympics crackfest…

I’m starting to say that Curling might be the best Olympic sport. Why?

  • It’s the most dominated by strategy. It also requires precision and grace, but above all the other Olympic sports, long pauses to think about the game are part of the game. If you haven’t guessed, I like strategy.
  • Yes, other sports have in-game strategy, of course, particularly the team sports. And since the gold medalist from 25 years ago in almost every sport would barely qualify, you can make a case that all the sports are mostly mental in their way. But with curling, it’s right there, and I think it edges out the others in how important it is.
  • While it requires precision and athletic skill, it does not require strength and endurance to the human limits. As such, skilled players of all ages can compete. (Indeed, the fact that out-of-shape curlers can compete has caused some criticism.) A few other sports, like sharpshooting and equestrian events, also demand skill over youth. All the other sports give a strong advantage to those at the prime age.
  • Mixed curling is possible, and there are even tournaments. There’s debate on whether completely free mixing would work, but I think there should be more mixed sports, and more encouragement of it. (Many of the team sports could be made mixed, of course mixed tennis used to be in the Olympics and is returning.)
  • The games are tense and exciting, and you don’t need a clock, judge or computer to tell you who is winning.

On the downside, not everybody is familiar with the game, the games can take quite a long time and the tournament even longer for just one medal, and compared to a multi-person race it’s a slow game. It’s not slow compared to an even that is many hours of time trials, though those events have brief bursts of high-speed excitement mixed in with waiting. And yes, I’m watching Canada-v-USA hockey now too.  read more »

A BIOS and OS designed for very fast booting (and aborting)

We all know how annoying it is that today’s much faster computers take such a long time to boot, and OS developers are working on speeding it up. Some time ago I proposed a defragmenter that notice what blocks were read in what order at boot and put the contiguous on the disk. I was told that experiments with this had not had much success, but more recently I read reports of how the latest Linux distributions will boot as much a 3 times faster on solid state disks as on rotating ones. There are some SSDs with performance that high (and higher) but typical ones range more in the 120 mb/second rate, better than 80 mb/second HDDs but getting more wins from the complete lack of latency.

However, today I want to consider something which is a large portion of the boot time, namely the power-on-self-test or “POST.” This is what the BIOS does before it gets ready to load the real OS. It’s important, but on many systems is quite slow.

I propose an effort to make the POST multitask with the loading of the real OS. Particularly on dual-core systems, this would be done by having one core do the POST and other BIOS (after testing all the cores of course) and other cores be used by the OS for loading. There are ways to do all this with one core I will discuss below, but this one is simple and almost all new computers have multiple cores.

Of course, the OS has to know it’s not supposed to touch certain hardware until after the BIOS is done initializing it and testing it. And so, there should be BIOS APIs to allow the OS to ask about this and get events as BIOS operations conclude. The OS, until given ownership of the screen, would output its status updates to the screen via a BIOS call. In fact, it would do that with all hardware, though the screen, keyboard and primary hard disk are the main items. When I say the OS, I actually mean both the bootloader that loads the OS and the OS itself once it is handed off to.

Next, the BIOS should, as soon as it has identified that the primary boot hard disks are ready, begin transferring data from the boot area into RAM. Almost all machines have far more RAM than they need to boot, and so pre-loading all blocks needed for boot into a cache, done in optimal order, will mean that by the time the OS kernal takes over, many of the disk blocks it will want to read will already be sitting in ram. Ideally, as I noted, the blocks should have been pre-stored in contiguous zones on the disk by an algorithm that watched the prior boots to see what was accessed and when.

Indeed, if there are multiple drives, the pre-loader could be configured to read from all of them, in a striping approach. Done properly, a freshly booted computer, once the drives had spun up, would start reading the few hundred megabytes of files it needs to boot from multiple drives into ram. All of this should be doable in just a few seconds on RAID style machines, where 3 disks striped can deliver 200mb/second or more of disk read performance. But even on a single drive, it should be quick. It would begin with the OS kernel and boot files, but then pre-cache all the pages from files used in typical boots. For any special new files, only a few seeks will be required after this is done.  read more »