The note combines (weak) control Lyapunov function-based nonlinear receding horizon control, with randomized optimization. This approach is applied to the problem of robot navigation in the presence of state and input constraints. It is shown that under certain conditions, relaxing the definiteness requirements on the terminal cost function allows one to select control inputs through a Monte-Carlo optimization scheme in a way that preserves the stability and convergence properties of the closed loop system. While the particular randomized optimization scheme used here can be substituted for the nonlinear optimal control method of choice, the introduction of randomization in receding horizon optimization is anticipated to offer additional trade-offs between performance and computation speed compared to the fixed-overhead nonlinear optimal control strategies typically employed.