I found an answer of sorts in the paper,
"Mean unknotting times of random knots and embeddings,"
by
Yao-ban Chan, Aleksander L Owczarek, Andrew Rechnitzer, and Gordon Slade
(<a href="http://iopscience.iop.org/1742-5468/2007/05/P05004">*Journal of Statistical Mechanics: Theory and Experiment*, Volume 2007, May 2007</a>.)
Here is the beginning of their Abstract:

> We study mean unknotting times of knots and knot embeddings by crossing reversals, in a problem motivated by DNA entanglement. Using self-avoiding polygons (SAPs) and self-avoiding polygon trails (SAPTs) we prove that the mean unknotting time grows exponentially in the length of the SAPT and at least exponentially with the length of the SAP.

Their SAPs are on a 3D lattice; their SAPTs are on a 2D lattice; see below.  Interesting that they did not
establish an upper bound for SAPs.
<br />
![SAPT][1]


  [1]: http://cs.smith.edu/~orourke/MathOverflow/SAPT.jpg