Go to the local city hall
Videomaker – Learn video production and editing, camera reviews › Forums › Technique › Miscellaneous Techniques › Interviewing People on the Street! › Go to the local city hall

Go to the local city hall they should have the forums. Also, if you are in front of a store talk to the manager first. Have the permit easy to get too so if anyone askes you can show it. If you can you should also have an assistant, they can handle that while you concentrate on what you are doing.
If it is a small town you may just need to let them know when/where and what you are doing, there may be no fee to pay. If in a mall, mall security will need to know and the mall manager. They may have their own permits and fees.
Get and use talent release forms.
Playing innocent may work but it is best to have permission first. 😉