The agreement is considered a precursor to disarmament.
Sudan's top government negotiator made the announcement at the talks in Obuja on Wednesday.
The talks had briefly hit an impasse on Tuesday when rebel movements refused to discuss being moved back to base by Sudanese government forces.
"They may need more forces, besides protection of their monitors, to help cantonment and protection of the rebels and we agree about that," said government negotiator Majdhoub al-Khalifa, who is also agriculture minister.
He said the exact number of troops would be decided later.
Sudan has already agreed to 300 AU troops in Darfur with a mandate to protect AU monitors of a widely disregarded ceasefire.
The proposal by AU chairman and Nigerian President Olusegun Obasanjo was to send some 2000 AU troops to garrison rebels, while Khartoum disarmed the Janjawid, whom Sudan referred to as "outlaws".
Having spent the first three days of talks in the Nigerian capital setting an agenda, the two sides adjourned until Thursday at 10am (0900 GMT) to begin formal negotiations on an accepted agenda.
The issue of disarmament and confining rebels to base will be addressed after that, and this will be followed by talks on political and socio-economic matters including development, negotiators said.
Rebel leaders, who almost brought the negotiations to a halt earlier on Wednesday, after they refused to discuss demobilising their forces ahead of a comprehensive political settlement.
"The article on talks on cantonment of our military is completely forbidden"
Abd al-Wahid Muhammad Ahmad al-Nur,
Leader of the rebel Sudan Liberation Movement (SLM)
The two rebel groups eventually sat down with Sudanese government envoys and AU mediators two-and-a-half hours late, and the talks broke up again barely an hour after a brief discussion of the humanitarian crisis in Darfur.
But rebel leaders said that they had agreed to shelve their objection to the inclusion of the African Union's proposed agenda for the talks of the "cantonment" of their armed forces until later in the proceedings.
Abd al-Wahid Muhammad Ahmad al-Nur, leader of the rebel Sudan Liberation Movement (SLM) had told reporters: "The article on talks on cantonment of our military is completely forbidden".
But al-Khalifa, said that the rebels must be disarmed and demobilised simultaneously with the Janjawid and that before talks on the Darfur region's future.
Khalifa also said the Janjawid had agreed to be be disarmed and the process had already begun.
The conflict in Darfur began as a land issue between nomadic tribes grazing their animals on land which local subsistence farmers claimed ownership of.
Two rebel groups from southern Sudan, the Sudan Liberation Movement (SLM) and the Justice and Equality Movement (JEM) stepped in and later the situation developed into an alleged ethnic conflict.
Abd al-Wahid Muhammad insisted
rebels will not accept cantonment
Both local and nomadic tribes claim they only retaliated.
Khartoum says the rebels exploited the situation and incited ethnic hatred for political gain.
Darfur, an area the size of France is said to be among the world’s most energy rich areas, which rebels claim the government has neglected.
In February 2003, the rebels claimed leadership of an uprising against Khartoum, whom they say is too Arab.
Rebel demands include direct involvement and control in the governing of Darfur and other provinces of oil-rich Sudan.
The UN says more than a million people have been displaced and upto 30,000 people have lost their lives in Darfur due to the conflict.