This paper presents an approximate multi-parametric Nonlinear Programming (mp-NLP) approach to explicit solution of feedback min-max NMPC problems for constrained nonlinear systems in the presence of bounded disturbances and/or parameter uncertainties. It is based on an orthogonal search tree structure of the state space partition and consists in constructing a piecewise nonlinear (PWNL) approximation to the optimal sequence of feedback control policies. Conditions guaranteeing the robust stability of the closed-loop system in terms of a finite l(2)-gain are derived. (C) 2009 Elsevier Ltd. All rights reserved.