Feb 26, 2010

Battery Voltage Regulation Prediction Software

It's rare that I can talk about green energy and software issues in one post.  Here's some software that someone needs to write.

Over at "This week in batteries", Venkat Srinivasan explains the tradeoffs in modern battery charging.  Essentially, the problem is that the higher voltage you charge a battery to, the bigger capacity it has in terms of discharging.  However, higher voltages at the same time reduce the lifespan of the battery so that the next charge will have a little less capacity.  Virtually all battery chargers choose a fixed voltage to charge up to and then stop charging, and this chosen voltage is a number that gives a good balance between capacity and lifespan, but doesn't really maximize either.  From the article:

Operating to 4.1V makes things better and extends the life, 4.0 V is even better and so on. So why don’t battery manufacturers cut the voltage off at, say, 4 V to get better battery life? Because every time you cut this voltage down you decrease the capacity of the battery and its run time. The 4.2V cutoff is a compromise between good run time and decent (read “not pathetic”) life.
Venkat goes on to suggest that this means you should charge your devices up to the maximum limit and then unplug them, so that they slowly drop a little below the max, to extend lifetime.  He also mentions that Lenovo laptops even let you set the charge (as a percentage, not a voltage) if you want to play with these settings yourself.

This is a problem not just for laptops, but also for cell phones, plug-in cars, or any device that uses a battery.  I'm certainly not a battery expert, but it seems to me that there is a better solution out there.

Most devices using an expensive battery have some amount of processing power and some amount of long-term memory (flash drive, hard drive, etc).  Laptop, Cell Phone, and Vehicles certainly fall in to this category.  If the device was able to predict roughly how long it would be used before the next recharge, then it would be able to charge to the lowest voltage required to stay alive until the next recharge.

Humans are creatures of habit, we often keep roughly the same schedule from day to day or week to week.  If the device kept a history of these habits, it should be able to predict usage.  For example, storing data like:

  • Plug in timestamp
  • Unplug timestamp
  • Running out of juice timestamp
  • Day of week, time of day
  • which user is logged in, or how much they weigh on the driver seat sensor
  • ip address the device is allocated to (or nearby wireless APs)
  • GPS location
  • applications that were run
Using a little bit of simple machine learning, the software could predict how much capacity is needed for the next unplug and chage accordingly.  Thus if the laptop is always plugged in at a desk except on the weekend, a low voltage charge could be maintained and then ramped up all the way saturday morning.  Or if the car is used for short trips to/from work, but on Friday night is driven to the next city for happy hour with friends, you can keep the voltage high for happy hour and low for the commute.  If the device sees a completely new scenario (suddenly turned on in Japan at 3am on a different network), then it might switch temporarily to a high voltage/capacity until enough data comes in to know what to expect in this new scenario.

This approach would maximize both battery life and capacity while keeping the user blissfully unaware.

Feb 5, 2010

Swoopo and stable equilibriums

If you've never heard of swoopo.com, it's an "auction" site that allows you to bid on items in 1c increments. Usually the items sell for much much less than they are worth.  For example, this 1oz gold bar (worth around $1,400) sold for $216.98.  The trick is that you can only bid exactly 1c more than the last bid and simply making a bid costs you $0.60.  So, 21,698 bids were made on that gold bar by various people which cost them over $13,018 in total.  The winner spent almost $700 in bids themselves.  Most people who play this game are losing lots of money.

A similar (simpler) game is described as an auction for a $20 bill.  The rule is that you pay your most recent bid, regardless of whether or not you win.  You can argue that it always makes sense for you to bid.  Initially, you are bidding $1 for a $20 bill, how awesome is that?  However your opponent in the auction can now bid $2 for a $20 bill, which he will definitely do - why wouldn't he?  At some point you have bid $19 for this bill, but your opponent recently just bid $18.  If he doesn't bid $20, he loses $18 - if he does bid $20 and wins, he comes out even.  So bidding $20 seems like the right choice.  Unfortunately now you lose $19 bid lost if you don't bid and you lose only $1 if you do bid (bid = $21, but you win $20).  So it makes sense for you to actually bid $21 for a $20 bill.  This continues forever with the risk that both participants bid hundreds of dollars for this $20 bill.

I was having a lunch conversation with some folks the other day who argued that the best choice at any turn is to always bid, but that this is a paradox because you will lose your shirt playing this game.  I think the paradox is easily resolved.  The thing that causes the paradox is the assumption that the best decision is to always bid, which seems on the surface to be the right strategy but in fact is not.  If you assume this is the right strategy, this game has no stable nash equilibrium, but I claim that the game does in fact have such an equilibrium strategy.

Imagine your opponent in this game (simplification - the game is a 2 player version of the $20 auction) is one instance of a set of players in the universe of possible players.  As such a player, there is a distribution of points in the auction where that player will stop bidding.  The number of players that will make it to $1 is high, say 99%, the number of players that make it past $20 is probably somewhat low, and the number of players that make it to $1 million is probably nearly zero.  As a result, you can evaluate at each point in the game what is the expected number of additional bids that you will have to make to gain the $20 bill.  If this is greater than 10 bids (an increase of $20 in your bidding), then you should not bid.  If it is less, then you should bid.  Depending on the distribution, you may choose not to even play the game or you may likely choose to play up to a few dollars or so because some reasonable fraction of other players give up early.  If you played enough such games, you would expect to come out non-negative however on some individual games you would expect to lose money.  My guess is that the real distribution for a $20 auction in the world of opponents would be such that not bidding at all makes sense, but if you make it a $1 million auction, then I would guess that due to finite budgets of your average opponent, it would make sense to bid up to some reasonable number and give up.

Interestingly, there are some distributions that would suggest you should never stop bidding.  For example if the probability that your opponent continues to bid decreases by 50% every time, then at any point in the game, you would expect to have to bid only 2 more times, meaning you should always keep bidding.  However, this is fine as long as your estimate of the distribution is correct because the odds of your opponent bidding 10 more times are tiny (1 in 1024).  So you are essentially betting on a fair coin toss repeatedly with a 1:10 payoff.

I have no idea what the distributions are for swoopo auctions.  If someone has the dataset, it would be interesting to analyze it and figure out the optimal strategy and see if it ever makes sense to bid (maybe it does in some cases).